# Sum of number of divisors of first N natural numbers

1. Mar 22, 2013

### suchith

If σ(N) is the sum of all the divisors of N and τ(N) is the number of divisors of N then what is the sum of sum of all the divisors of first N natural numbers and the sum of the number of divisors of first N natural numbers?

Is there any relation between σ(N) and τ(N) functions?

Can I do that without factorizing any of the number in the sequence?

2. Mar 22, 2013

### HallsofIvy

Staff Emeritus
Have you tried calculating those yourself up to, say, N= 100?

3. Mar 22, 2013

### suchith

Of course I have using my computer. I don't remember the result now. I have tried for both. Well!! Using computer it is not a big job.

But can I find it out without listing the factors or factorizing individual numbers?

Avoiding factorization is the goal. I wrote these functions in the form of series, for sum of tau function in the form of infinite series without factorization, and for sum of sigma function it is a finite series. I have written the proof by myself, but don't know about the correctness. Is there anything to find the sum in the mathematical literature?

4. May 7, 2015

### geoffrey159

You can explicitly calculate $\sigma(n)$ and $\tau(n)$, but you will need the prime decomposition of $n$, say $n = \prod_{i=1}^N p_i^{r_i}$.

The positive divisors of $n$ are $\text{Div}(n)=\{ p_1^{q_1} \times ... \times p_N^{q_N},\ 0\le q_i \le r_i,\ i = 1...N \}$

There is an obvious bijection between $\text{Div}(n)$ and $\{ q_1,\ 0\le q_1 \le r_1\} \times ... \times\{ q_N,\ 0\le q_N \le r_N\}$ wich contains $\prod_{i = 1}^N (1+r_i)$ elements.

So $\tau(n) = \#\text{Div}(n) = \prod_{i = 1}^N (1+r_i)$

And $\sigma(n) = \sum_{q_1 = 0 }^{r_1}...\sum_{q_N = 0}^{r_N} p_1^{q_1} \times ... \times p_N^{q_N} = \prod_{i=1}^N \sum_{q_i = 0}^{r_i} {p_i}^{q_i} = \prod_{i=1}^N \frac{1 - p_i^{r_i+1}}{1-p_i}$

5. Aug 22, 2015

### Anakar Parida

@geoffrey159 and @Suchit I do understand how to calculate τ(n) but didn't get how to calculate τ(N). I will highly appreciate if someone can give the programming algorithm for the problem.