Perfect numbers, part II

In my last post I introduced the concept of perfect numbers, which are positive integers n for which $\sigma(n) = 2n$ , where $\sigma(n)$ denotes the sum of all the divisors of n. Incidentally, we could write the definition of $\sigma(n)$ as

$\displaystyle \sigma(n) = \sum_{d|n} d$ ,

that is, the sum ranging over all d for which d divides n ( $d|n$ ). Of course, this is slightly nonstandard $\sum$ -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, $\sigma_k (n)$ is used to denote the sum of the kth powers of the divisors of n, that is,

$\displaystyle \sigma_k (n) = \sum_{d|n} d^k.$

For example, $\sigma_3(6) = 1^3 + 2^3 + 3^3 + 6^3 = 252$ . So, the function that we have been calling $\sigma(n)$ is really $\sigma_1(n)$ , and $\sigma_0(n)$ 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 $\sigma(n)$ , assuming that n can be factored as $n = p_1^{\alpha_1}p_2^{\alpha_2} \dots p_m^{\alpha_m}$ :

$\displaystyle \sigma(n) = \prod_{i=1}^m \frac{p_i^{\alpha_i+1} - 1}{p_i - 1}.$

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:

$\sigma(18) = 2^03^0 + 2^03^1 + 2^03^2 + 2^13^0 + 2^13^1 + 2^13^2 = 39.$

Do you see the pattern? 18 can be factored as $2^1 3^2$ , and every divisor of 18 is of the form $2^r 3^s$ , where $0 \leq r \leq 1$ and $0 \leq s \leq 2$ . 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 $2^2$ 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 $2^r 3^s$ for every possible combination of values for $0 \leq r \leq 1$ and $0 \leq s \leq 2$ .

There’s nothing special about 18 here, of course. In general, if we have $n = p_1^{\alpha_1}p_2^{\alpha_2} \dots p_m^{\alpha_m}$ , then every divisor of n will be of the form $p_1^{\beta_1} p_2^{\beta_2} \dots p_m^{\beta_m}$ , where $0 \leq \beta_i \leq \alpha_i$ (that is, each $\beta_i$ falls between 0 and the corresponding $\alpha_i$ , inclusive). We get every divisor exactly once if we take all possible combinations of values for the $\beta_i$ ‘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:

$\displaystyle \begin{array}{rcl} \sigma(18) & = & 2^03^0 + 2^03^1 + 2^03^2 + 2^13^0 + 2^13^1 + 2^13^2 \\ & = & 3^0(2^0 + 2^1) + 3^1(2^0 + 2^1) + 3^2(2^0 + 2^1) \\ & = & (2^0 + 2^1)(3^0 + 3^1 + 3^2) \end{array}$

In other words, to get a divisor of 18, first choose a power of 2 $(2^0 + 2^1)$ and then choose a power of 3 $(3^0 + 3^1 + 3^2)$ ; multiplying these expressions gives us the sum of all possible choices. In the general case, the sum of all divisors of the form $p_1^{\beta_1} p_2^{\beta_2} \dots p_m^{\beta_m}$ , for all possible combinations of values for the $\beta_i$ ‘s, can be factored as:

$\sigma(n) = (1 + p_1 + p_1^2 + \dots + p_1^{\alpha_1}) \cdots (1 + p_m + p_m^2 + \dots + p_m^{\alpha_m}).$

The dots in the middle indicate that there is one term $(1 + p_i + p_i^2 + \dots + p_i^{\alpha_i})$ for every different prime $p_i$ . Again, this represents first choosing a power of $p_1$ , then choosing a power of $p_2$ , and so on up to $p_m$ ; multiplying all of these terms gives us the sum of all possible choices. As an example, consider $n = 720 = 2^4 3^2 5$ : we obtain

$\begin{array}{rcl} \sigma(720) & = & (2^0 + 2^1 + 2^2 + 2^3 + 2^4)(3^0 + 3^1 + 3^2)(5^0 + 5^1) \\ & = & (1 + 2 + 4 + 8 + 16)(1 + 3 + 9)(1 + 5) \\ & = & 31 \cdot 13 \cdot 6 = 2418. \end{array}$

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 $S = 1 + p_i + p_i^2 + \dots + p_i^{\alpha_i}$ . You may recognize this as a geometric series, a sum of terms where each term is a constant multiple of the previous. Note that $p_iS = p_i + p_i^2 + \dots + p_i^{\alpha_i} + p_i^{\alpha_i + 1}$ , so if we subtract S from this, all the terms cancel out except for the first and last, giving

$p_iS - S = p_i^{\alpha_i + 1} - 1,$

and therefore

$\displaystyle S = \frac{p_i^{\alpha_i + 1} - 1}{p_i - 1}.$

Looks familiar, doesn’t it? Sure it does! Now do you see where the formula for $\sigma(n)$ comes from?

Next up: finding more perfect numbers!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

8 Responses to Perfect numbers, part II

DB says:

November 16, 2007 at 12:37 pm

Of course! So simple, now that you explained it! Thanks for a really fun and well-written blog.

P.S. There’s a typo: you said 2^r 3^2 when you meant 2^r 3^s, in the paragraph that starts, “Do you see the pattern?”
Jonathan says:

November 17, 2007 at 10:57 am

I understood these last two posts! What powerful notations exist in math; it feels like programming languages did not so much invent anything as they did translate it. You do a great job translating math, Brent, thanks so much.
Brent says:

November 17, 2007 at 4:40 pm

@DB: Thanks for the kind words! And thanks for the typo catch, I’ve fixed it now.

@Jonathan: Hooray! These last two posts were a bit more notation-heavy/technical than usual so I’m very glad to hear that it made sense to people. And your statement about programming languages is more true than you know; the theory behind computers and programming languages always has been, and still is, heavily based in mathematics.
Jonathan says:

November 24, 2007 at 8:32 pm

I was reading the other Jonathan’s comment, and getting confused. I know it sounds right, but I know I didn’t write that.

The factoring bit is very nice. I think I will give my combinatorics class a day off next week – I’ll steal some of your perfect number material, do some work, and let them search a bit…

Thanks!

(other) Jonathan
Brent says:

November 25, 2007 at 12:12 am

Jonathan: excellent, steal away. Let me know how your combinatorics class does with it! Perhaps I will write about Catalan numbers sometime…

heh, I know the other Jonathan (a friend from college) wasn’t you; I can tell since I can see posters’ e-mail addresses, although they don’t show up on the comments page.
Zan says:

January 4, 2008 at 8:41 pm

Brent– I found your page somehow a while ago and am enjoying the posts, especially this one. As a child, 6 was my favorite number because it was perfect (evidently this is what happens when one has math teachers for parents). I hope that all is well with you!
-Zan
Brent says:

January 7, 2008 at 3:18 pm

Hi Zan! Glad you’re enjoying the posts. =) That’s really cute, lacking math-teacher parents I don’t think I even knew what perfect numbers were until middle school or so.

I’m doing well, just finished applying to PhD programs in CS, now I just have to wait… hope you’re well too!
Jaime Montuerto says:

December 12, 2008 at 3:13 am

Hi,

It’s beautiful, simple and elegant. Writing ideas this way makes creates bridge to a lot of math enthusiast. Truly appreciates this blog.

I am not a math expert but love math secret mysteries like these. Now I see some interesting relationship between additive and multiplicative structure of numbers. Are there more structures that can be described like this?

Personally I am working on the mysteries of Mersenne numbers and its relationship with prime numbers. I observed that there is a close relationship between the two numbers. It’s not surprising that Mersenne numbers exhibit these properties. Like relationship with perfect numbers, wagstaff prime numbers and I believed in all prime numbers.

Looking forward for more post.