7
$\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
    Am I missing an obvious patter in your column on the right?2010-09-27
  • 0
    @BBischof, the values on the right are $D(n)$, e.g. $D(1)=1$, $D(2)=3$, $D(3)=5$, $D(4)=8$, etc.2010-09-27
  • 0
    I've swapped n and x in the divisor summatory function.2010-09-27
  • 0
    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.2010-09-27
  • 0
    @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.)2010-09-27
  • 0
    Downvoted because I don't like this form of question. Which goes: is this a known formula/fact/etc. It is better to learn how to prove results than finding out if they are known by some authority. When you see how to prove things you can see that these results are trivial at a glance - or notice when they are interesting in the cases that they are.2010-09-27
  • 0
    I edited the text to indicate how to interpret the values on the right.2010-09-27
  • 0
    @A. Neves (and possibly @muad) I want to say that I partially agree with muad. In the sense that I don't like the way the question was posed. Had you asked "I found this pattern, and I expect that it is true in general, is there a way to see this?" I would be more pleased. Yours comes across a bit more braggart. Keep in mind that an even better of the above rephrasing would of been "I have seen this pattern, but cannot seem to prove it holds in general. I have tried blah blah blah, and my reasons for thinking that it is true in general are blah, so is my reasoning correct?".2010-09-27
  • 0
    I edited my question to clarify where it comes from.2010-09-27

2 Answers 2

5

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.