Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $d(n)$ represent the divisor function as


and the divisor summatory function as

$D(x)=\displaystyle\sum\limits_{n \leq x}d(n)$

I found the following triangular representation for the values of $D(n)$

$$ \begin{array}{ccccccccc} D(1)=&&&&&&&&& 1 &&&&&&&&&&=1\\ &\\ D(2)=&&&&&&&& 2 &+& 1 &&&&&&&&&=3\\ &\\ D(3)=&&&&&&& 3 &+& 1 &+& 1 &&&&&&&&=5\\ &\\ D(4)=&&&&&& 4 &+& 2 &+& 1 &+& 1 &&&&&&&=8\\ &\\ D(5)=&&&&&5 &+& 2 &+& 1 &+& 1 &+& 1&&&&&&=10\\ &\\ D(6)=&&&&6 &+& 3 &+& 2 &+& 1 &+& 1 &+& 1&&&&&=14\\ &\\ D(7)=&&&7 &+& 3 &+& 2 &+& 1 &+& 1 &+& 1&+& 1 &&&&=16\\ &\\ D(8)=&&8 &+& 4 &+& 2 &+& 2 &+& 1 &+& 1&+& 1&+&1&&&=20\\ &\\ \end{array} $$

The values on the right are the sum of all elements in a row.


The above picture is the result of the following observation:

Let $v_{m}(n)$ be the greatest power of $m$ that divides $n$ with $ m,n \in \mathbb{N}$ , so we get that

$D(n)=\displaystyle\sum\limits_{m=2}^{\infty}v_{m}(p^{n}), p \in \mathbb{P}$ where $p$ is a fixed prime number.

I didn't try to prove this. I don't know how to do it, but hopefully some one will have some idea on how to prove or disprove this conjecture.

I'd like to know if this is a known fact. I don't have a proof but I've tested lots of values and woks all the time.


share|cite|improve this question
Am I missing an obvious patter in your column on the right? – BBischof Sep 27 '10 at 15:22
@BBischof, the values on the right are $D(n)$, e.g. $D(1)=1$, $D(2)=3$, $D(3)=5$, $D(4)=8$, etc. – Neves Sep 27 '10 at 15:26
I've swapped n and x in the divisor summatory function. – anon Sep 27 '10 at 15:32
The values in the triangle are just the quotient of dividing the row number by the column number, so it's no surprise that this gives the sum of divisors. – anon Sep 27 '10 at 15:36
@A.Neves: I assume the downvote is because the pattern in the triangle isn't clear. You should state explicitly what it is. (For those who can't see it, read the diagonals from the top right to the bottom left.) – Qiaochu Yuan Sep 27 '10 at 16:38
up vote 5 down vote accepted

Yes, this is true. Write $D(x) = \sum_{n \le x} d(n) = \sum_{n \le x} \sum_{d | n} 1 = \sum_{d \le x} \lfloor \frac{x}{d} \rfloor$; this is equivalent to the pattern you observe. The last step is exchanging the order of summation together with the observation that the number of times a number $d$ appears in the double sum is the number of numbers less than or equal to $x$ it divides.

share|cite|improve this answer
thats true, I already knew that way of calculating $D(x)$, but as I came to this observation from another path I never looked at the triangle as a result of $\sum_{d \leq x}\lfloor\frac{x}{d}\rfloor$, but thats true, the values in the triangle are "just the quotient of dividing the row number by the column number". – Neves Sep 27 '10 at 17:10

This answer is a bit of a work in progress, but if $n=2^x-1$, then $$\frac{D(n)+u}{2}=\sum_{j\in\mathcal{N}}\sum_{i=1}^{n}{h_{i,j}} \text{ where } u=\lfloor\sqrt{n}\rfloor$$

where $h_{i,j}$ is the value in the corresponding row,column of the matrix described in

Furthermore, letting $r_j=\sum_{i\in\mathcal{N}}{h_{i,j}}$, we write:

$$ D(2^k-1)=u-\xi+2\sum_{l=0}^{k-1}\frac{(k-l+1)(k-l)}{2}\sum_{j=\lfloor 2^{l-1}\rfloor }^{2^l-1}{r_j} $$

where $\xi$ is computed using the program:

input k
unsigned step = 1
unsigned y = 1
unsigned $\xi$ = 0
while y < 2^k {
    unsigned bin=(unsigned)log2(y)
    $\xi$ = $\xi$ + (k-bin)(k-bin+1-(k-bin)%2)
    y = y + 8* step
    step = step + 1
output $\xi$

This suggests a slim possibility of computing $D(x)$ in $log_2(x)$ time.

share|cite|improve this answer

Your Answer


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.