Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sum of number of divisors of first N natural numbers

  1. Mar 22, 2013 #1
    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. jcsd
  3. Mar 22, 2013 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Have you tried calculating those yourself up to, say, N= 100?
     
  4. Mar 22, 2013 #3
    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?
     
  5. May 7, 2015 #4
    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}##
     
  6. Aug 22, 2015 #5
    @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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Sum of number of divisors of first N natural numbers
Loading...