1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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...