8
$\begingroup$

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.

  • 0
    I edited my question to clarify where it comes from.2010-09-27

2 Answers 2

6

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.

  • 0
    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".2010-09-27
1

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 https://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.