Out for a run, I listened to A Podcast Of Unnecessary Detail talking about amicable numbers, and I wondered if I could use generating functions to sum the factors of an integer.

I know, now I have ( 1 + x ) problems. While GF underlie this, I’m not going to use them explicitly here.

If I wanted to work out the factors of 12 by hand, I would find its prime factorisation, (2^2 \times 3^1) and list every distinct choice for (2^a 3^b) with (0 \le a \le 2) and ( 0 \le b \le 1 ). There are six of those, as we’d expect.

But we can set that bit of combinatorics up as a product: if we worked out ((1+2+4)(1+3)) by expanding before adding, we’d get six terms, all different, all factors of 12 – we’ve got them all!

If we do it the sensible way, adding first, we get ( 7 \times 4 = 28\ ), which is indeed the sum of the factors of 12. (To get the sum of proper factors, we’d just subtract 12 at the end.)

We can do better than this.

Each of the factors – in general, not just for 12 – is a geometric sequence. If one of the prime-power factors of our number is $p^k$, then the corresponding factor is ( 1+ p + p^2 + \dots + p^k), which is ( \frac{p^{k+1}-1}{p-1) ).

So, if we want to sum the factors of an integer ( p_1^{k_1} p_2^{k_2} \dots p_n^{k_n} ) to get ( S ), we simply multiply together all of those geometric sequences: ( S = \Pi_{i=1}^n \frac{p_i^{k_i}-1}{p_i-1} ).

For example, if we take ( 220 = 2^2 \times 5 \times 11 ), we get (S = \frac{2^3-1}{2-1} \times \frac{5^2-1}{5-1} \times \frac{11^2-1}{11-1}), or ( \frac{7}{1} \times \frac{24}{4} \times \frac{120}{10} ); that’s ( 7 \times 6 \times 12 = 504 ) – that’s the sum of all of 220’s factors; the sum of its proper factors is ( 504- 220 = 284 ). Nice!