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.

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.

share|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
3  
When voting down, please, explain why. –  Neves Sep 27 '10 at 16:23

2 Answers 2

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

$$ D(n)=\sum_{k=1}^{\lfloor\sqrt{n}\rfloor}\left(2 \cdot \left\lfloor \frac{n-k^2}{k}\right\rfloor+1\right) $$

javascript version

share|improve this answer

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.