The Divisor Function Sigma

January 10, 2014

In number theory, the divisor function σx(n) is the sum of the xth powers of the divisors of n. For instance, the divisors of 60 are 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 and 60, so σ0(60) = 12 (the count of the divisors, sometimes called τ(n)), σ1(60) = 168 (the sum of the divisors, sometimes called σ(n) without the subscript), and σ2(60) = 5460. The divisor function is fundamental to much of number theory, and there are many identities and formulas that make use of it, as in the MathWorld article. To calculate the divisor function σx(n), first calculate the prime factorization n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k}, then \sigma_x(n) = 1 if n = 1 (regardless of the value of x), \sigma_x(n) = \prod_{i=1}^k (a_i + 1) if x = 0 and \sigma_x(n) = \prod_{i=1}^k \frac{p_i^{(a_i+1)x}-1}{p_i^x-1} if x > 0.

The summatory divisor function calculates the sum of the values of the divisor function from 1 to n; that is \sum_{d=1}^n \sigma_x(n). It could be calculated by summing the values of each of the divisor functions from 1 to n, but a better approach considers for each divisor how many times it appears in the summation: divisor 1 appears for each number from 1 to n, divisor 2 appears for half of them, divisor 3 appears for a third of them, and divisor d appears in ⌊n / d⌋ of them. Arranged in this way, it is easy to calculate the summatory divisor function in linear time.

Your task is to write the divisor and summatory-divisor functions described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisement

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
1 Comment »