## The Divisor Function Sigma

### January 10, 2014

In number theory, the divisor function σ_{x}(*n*) is the sum of the *x*th 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 `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.