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 , then if (regardless of the value of x), if and if .
The summatory divisor function calculates the sum of the values of the divisor function from 1 to n; that is . 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
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.