sum of divisors

Finding the sum of the divisors of n

Last week, we found an efficient way to calculate D(n), the number of divisors of n. This week, we turn to the problem of finding a better way to calculate the sum S(n) of all the divisors of n.

For example, suppose we want to find the sum of the divisors of n = 144.

As we did last week, we begin by forming the prime factorization of 144:

144 = 24 . 32.

Any divisor of 144 must be a product of some number of 2's (between 0 and 4) and some number of 3's (between 0 and 2). So here's a table of the possibilities:

    20  21  22  23  24  Row sum
30  1   2   4   8   16  31
31  3   6   12  24  48  93
32  9   18  36  72  144     279
Column sum  13  26  52  103     206     403

Notice in the table that the first column sum is 1+3+9=13. And the other column sums are 13 . 2, then 13 . 4, and so forth.

So the total is the product of 1 + 3 + 9 =13 with 1 + 2 + 4 + 8 + 16 = 31.

Notice that we could write the true equation that:

S(144) = S(24 . 32) = S(24) . S(32).

In general, if you have the prime factorization of the number n, then to calculate the sum of its divisors, you take each different prime factor and add together all its powers up to the one that appears in the prime factorization, and then multiply all these sums together!

Example: Determine S(1800).

Solution: The prime factorization of 1800 is 23 . 32 . 52. And

S(23) = 1 + 2 + 4 + 8 = 15
S(32) = 1 + 3 + 9 = 13
S(52) = 1 + 5 + 25 = 31

Therefore S(1800) = 15 . 13 . 31 = 6045.

One last thing that would help is to have a formula for calculating

S(pk) = 1 + p + p2 + . . . + pk

Here it is (we'll talk about why it's true in class):

S(pk) = 1 + p + p2 + . . . + pk = (pk+1 - 1) / (p-1) .

One for you: Calculate S(1,000,000).