Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.