# A triangular representation for the divisor summatory function, $D(x)$

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

$d(n)=\displaystyle\sum\limits_{k|n}1$

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.

EDIT 1:

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.

Thanks.

-
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

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.

-
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 http://crypto.stackexchange.com/questions/27003/has-anyone-heard-of-matrix-based-roman-doll-encryption-techniques

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.

-