In my last post I introduced the concept of perfect numbers, which are positive integers n for which , where denotes the sum of all the divisors of n. Incidentally, we could write the definition of as
that is, the sum ranging over all d for which d divides n (). Of course, this is slightly nonstandard -notation; usually there is some sort of index variable which counts by ones from a starting to an ending value, but here the index varaible, d, doesn’t count by ones but instead only takes on values that evenly divide n. This notation is actually fairly common, though, and there’s not really any chance of confusion.
While I’m on a tangent, I should also mention that in general, is used to denote the sum of the kth powers of the divisors of n, that is,
For example, . So, the function that we have been calling is really , and tells how many divisors n has, instead of giving their sum (do you see why?).
Now, as you may recall, in my last post I claimed the following formula for calculating , assuming that n can be factored as :
But I didn’t explain where this formula comes from! Well, today I’d like to rectify that. Let’s start with an example: let’s add up all the divisors of 18. Simple enough: 1 + 3 + 9 + 2 + 6 + 18 = 39. But we can write this in a slightly different form which shows more clearly what is going on:
Do you see the pattern? 18 can be factored as , and every divisor of 18 is of the form , where and . This makes sense — clearly, any divisor of 18 can only use the same prime factors that 18 has, and a given prime factor must occur between zero times and the number of times it occurs in 18 (since otherwise we wouldn’t get a divisor — for example, nothing with a factor of can be a divisor of 18). In fact, we can make a stronger statement than this: we can obtain every single divisor of 18 exactly once by taking for every possible combination of values for and .
There’s nothing special about 18 here, of course. In general, if we have , then every divisor of n will be of the form , where (that is, each falls between 0 and the corresponding , inclusive). We get every divisor exactly once if we take all possible combinations of values for the ‘s.
Now, going back to our example of adding up the divisors of 18 for a moment: notice that we can factor it nicely, like so:
In other words, to get a divisor of 18, first choose a power of 2 and then choose a power of 3 ; multiplying these expressions gives us the sum of all possible choices. In the general case, the sum of all divisors of the form , for all possible combinations of values for the ‘s, can be factored as:
The dots in the middle indicate that there is one term for every different prime . Again, this represents first choosing a power of , then choosing a power of , and so on up to ; multiplying all of these terms gives us the sum of all possible choices. As an example, consider : we obtain
You can verify for yourself that this is, in fact, the sum of all the divisors of 720! OK, we’re almost there. The only step that remains is to simplify the sums of the form . You may recognize this as a geometric series, a sum of terms where each term is a constant multiple of the previous. Note that , so if we subtract S from this, all the terms cancel out except for the first and last, giving
Looks familiar, doesn’t it? Sure it does! Now do you see where the formula for comes from?
Next up: finding more perfect numbers!