Determine if $\sum_{q=1}^{\lceil n/2\rceil}R_q(n)$ gives the number of divisors of $n$.

51 Views Asked by At

Let $$R_q(n)=\left\{\begin{array}{lll} r\left(\dfrac n{2q-1}\right)&\text{if }(2q-1)\mid n\\ 0&\text{otherwise}\end{array}\right\},$$

where $r(n)$ is the ruler function, i.e., the $2$-adic valuation of $2n$.

Determine if

$$d(n)=\sum_{q=1}^{\lceil n/2\rceil}R_q(n),$$

where $d(n)$ is the number of divisors of $n$.

1

There are 1 best solutions below

2
On BEST ANSWER

First consider powers of $2$:

$$\sum_{q=1}^{2^{n-1}}R_q(2^n)=r(2^n)=n+1=d(2^n)\;.$$

Now consider an odd number $2m-1$, where $m\in\Bbb Z^+$:

$$\large\sum_{q=1}^mR_q(2m-1)=\sum_{{k\mid 2m-1}\atop{k\ge 1}}r(k)=\sum_{{k\mid 2m-1}\atop{k\ge 1}}1=d(2m-1)\;.$$

Finally, consider $2^nm$, where $m$ is odd and $n\ge 1$:

$$\large\sum_{q=1}^{2^{n-1}m}R_q(2^nm)=\sum_{{k\mid m}\atop{k\ge 1}}r(2^nk)=\sum_{{k\mid m}\atop{k\ge 1}}(n+1)=(n+1)d(m)=d(2^nm)$$

by the multiplicativity of $d$. I also use the fact that the odd divisors of $2^nm$ are precisely the odd divisors of $m$.