# Why the sum of the greatest powers results in $D(n)$ for numbers $p^k$?

The following table contains the greatest powers of $m$ that divide $n$,

$$\begin{matrix} & & 01 & 02 & 03 & 04 & 05 & 06 & 07 & 08 & 09 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & \\ & & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow& \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \\ 2 & \rightarrow & 0 & 1 & 0 & 2 & 0 & 1 & 0 & 3 & 0 & 1 & 0 & 2 & 0 & 1 & 0 & 4 & \cdots \\ 3 & \rightarrow & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 2 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & \cdots \\ 4 & \rightarrow & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 2 & \cdots \\ 5 & \rightarrow & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & \cdots \\ 6 & \rightarrow & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & \cdots \\ 7 & \rightarrow & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & \cdots \\ 8 & \rightarrow & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & \cdots \\ 9 & \rightarrow & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \cdots \\ 10 & \rightarrow & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & \cdots \\ 11 & \rightarrow & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & \cdots \\ 12 & \rightarrow & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & \cdots \\ 13 & \rightarrow & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & \cdots \\ 14 & \rightarrow & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & \cdots \\ 15 & \rightarrow & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & \cdots \\ 16 & \rightarrow & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & \cdots \\ & & \vdots & & & & & & & \vdots & & & & & & & & \vdots & \\ \{D(n)\}& = & \lbrace & 1, & & 3, & & & & 5, & & & & & & & & 8,& \cdots\rbrace \\ \end{matrix}$$

On the bottom we have the sum of the powers corresponding to numbers of the form $2^k$, we can see that this sequences corresponds to the values of the Divisor Summatory Function, $D(n)$. I have tested this one milion and it holds. If we do this for numbers of the form $p^k$ we get the same sequence ($p$ is a prime number). I have devised a formula for $D(n)$ that uses this observation $$D(n)=\sum_{m=2}^{\infty}\sum_{r=1}^{\infty}\frac{r}{m^{r+1}}\sum_{j=1}^{m-1}\left(\sum_{k=0}^{m^{r+1}-1}\cos\left( \frac{2k\pi(2^{n}+(m-j)m^{r})}{m^{r+1}} \right)\right)$$

This table assumes another form (simplified) in this previous question.

So, why the sum of the greatest powers results in $D(n)$ for numbers $p^k$?

-
I don't know about your $D(n)$, but the column sum for $n=p^k$ is independent of $p$, and equal to $\sum_{i=1}^k \lfloor \frac{k}{i} \rfloor$ –  Thomas Andrews Oct 21 '11 at 15:47

Let $o(m,n)$ be the largest $i$ such that $m^i|n$.

Define $O(n) = \sum_{m=2}^n o(m,n)$.

You also have $D(n) = \sum_{m=1}^n \tau(m) = \sum_{m=1}^n \sum_{d|m} 1$.

Then, for $p$ prime and $k\geq 1$ we have:

$$O(p^k) = D(k)$$

Proof: $o(m,p^k)$ is equal to $0$ if $m$ is not a power of $p$, and, if $m=p^i$, then $o(p^i,p^k)= \lfloor \frac{k}{i} \rfloor$. So, as I noted in my comment above:

$$O(p^k) = \sum_{i=1}^{k} \lfloor \frac{k}{i} \rfloor$$

Now, re-arrange $D(k)$ as:

$$D(k) = \sum_{d=1}^k \sum_{d|m; m\leq k} 1$$

So $\sum_{d|m; m\leq k} 1$ is just the number of multiples of $d$ which are at most $k$, which is clearly $\lfloor \frac{k}{d}\rfloor$

So $$D(k) = \sum_{d=1}^k \lfloor \frac{k}{d}\rfloor$$ hence $D(k)=O(p^k)$.

Now, what that horrible summation at the end of your question has to do with this problem is unclear.

-
It is not clear to me why $o(p^i,p^k)= \lfloor \frac{k}{i} \rfloor$. –  Neves Oct 21 '11 at 17:42
@Neves: When is $(p^i)^j=p^{ij}$ a divisor of $p^k$? Precisely when $ij\leq k$. So the maximum $j$ is $\lfloor \frac{k}{i} \rfloor$ –  Thomas Andrews Oct 21 '11 at 17:49