Perfect numbers, part I

Today I’d like to talk about perfect numbers, which touch on some clever algebra and some neat topics in number theory. At least, I’ll start talking about them, since it will probably take me three or four posts to say everything I want to say. =)

Without further ado, the definition of perfect numbers is very simple: a number n is perfect if its proper divisors add up exactly to n. A divisor of n, of course, is a number which evenly divides n; talking about the “proper” divisors of n simply excludes n itself. For example, the proper divisors of 6 are 1, 2, and 3, which have the sum 1 + 2 + 3 = 6 — so 6 is a perfect number. An equivalent way of expressing the definition is that n is perfect if all its divisors (including n itself) add up to twice n. The sum of all the divisors of n is often written \sigma(n), so formally, we can write that n is perfect if \sigma(n) = 2n.

The next perfect number after 6 is 28 (28 = 1 + 2 + 4 + 7 + 14), and the next after that is 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248. Are there any more? Well, that’s what I’d like to talk about. Today I’ll start by showing how we can easily compute \sigma(n).

How would you compute, say, \sigma(504)? One way would be to simply check every number from 1 to 252 to see which ones divide 504, and add them up. (252 is half of 504, so there clearly can’t be any larger proper divisors of 504.) However, that’s tedious and error-prone. It seems like there should be a better way.

As you know, we can write any integer in terms of its prime factorization: for example, 504 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 7. We can also simplify this further by collecting like primes: 504 = 2^3 \cdot 3^2 \cdot 7. In general, we can write any number n in the form

n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_m^{\alpha_m},

where p_1, p_2, \dots, p_m are m different prime numbers, and the \alpha_i‘s are all positive integer powers. In the case of 504, for example, we would have p_1 = 2, p_2 = 3, p_3 = 7 and \alpha_1 = 3, \alpha_2 = 2, \alpha_3 = 1.

Now, I claim that if n is factored in the form above, then

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

[Incidentally, are you one of those people who freaks out when you see a scary-looking equation like the one above? Well, stop it this instant! If you think something is too scary or complicated for you to understand, then you’re absolutely right–because you haven’t even given yourself a chance. But if you force yourself to get over your initial fear, take a good hard look, and consider it slowly in small pieces, you might be surprised at how much you can understand after all.]

Big Pi (\prod) is just like Big Sigma (\sum), except that it denotes a product instead of a sum. You can read more about sigma and big pi notation here. In this case, the formula for \sigma(n) just means that for each p_i^{\alpha_i} in the factorization of n, we compute (p_i^{\alpha_i + 1} - 1)/(p_i - 1), and then multiply them all together. As an example, we can compute \sigma(504):

\begin{array}{rcl} \sigma(504) & = & \frac{2^4 - 1}{2-1} \cdot \frac{3^3 - 1}{3 - 1} \cdot \frac{7^2 - 1}{7 - 1} \\ & = & \frac{15}{1} \cdot \frac{26}{2} \cdot \frac{48}{6} = 15 \cdot 13 \cdot 8 = 1560. \end{array}

Let’s also try it on 6 = 2 \cdot 3 and 28 = 2^2 \cdot 7. We know this should yield 12 and 56 respectively, since \sigma(n) = 2n for perfect numbers.

\begin{array}{rcl} \sigma(6) & = & \frac{2^2 - 1}{2 - 1} \cdot \frac{3^2 - 1}{3 - 1} \\ & = & 3 \cdot 4 = 12, \qquad \text{and} \\ \sigma(28) & = & \frac{2^3 - 1}{2 - 1} \cdot \frac{7^2 - 1}{7 - 1} \\ & = & 7 \cdot 8 = 56. \end{array}

It works! OK, now it’s your turn: can you use this method to compute \sigma(8128)?

The question you should be asking at this point is: why does this work? Where did this crazy-looking formula for \sigma(n) come from? That’s what I’m going to talk about next time. And after that, I’ll show how this formula can help us discover more perfect numbers.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in famous numbers, number theory, sequences. Bookmark the permalink.

3 Responses to Perfect numbers, part I

  1. MathMom says:

    The way I first saw the formula for \sigma(n) where n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_m^{\alpha_m} is:

    \displaystyle \sigma(n) = (p_1^0 + p_1^1 + \dots + p_1^{\alpha_1}) \times \dots \times (p_m^0 + p_m^1 + \dots + p_m^{\alpha_m})

    (Yes, I could have written that more efficiently as a combination of Big Pi and Big Sigma notations, but writing it out makes it a bit more clear what is going on, and why it works.)

    Now the trick is just to prove that your formula for \sigma(n) is equivalent to mine. 😉

  2. Brent says:

    MathMom: right, that’s exactly where the formula for \sigma(n) that I gave comes from! I plan to write about that in my next post.

    (I took the liberty of fixing your LaTeX: to get LaTeX on my blog you delimit it with [ tex ] and [ /tex ] (without the spaces). I’ve had LaTeX support on my blog long before had it, so now that everyone is used to the ... form, it’s too late to change mine. =(

  3. Pingback: Perfect age « The Math Less Traveled

Comments are closed.