1
$\begingroup$

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$?

  • 0
    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 $2011-10-21

1 Answers 1

3

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.

  • 0
    @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$2011-10-21