Perfect numbers, part III

Posted on November 27, 2007 by Brent

This is the last in a series of posts about perfect numbers. A quick recap of the series so far: in part I, I defined perfect numbers as positive integers n for which $\sigma(n) = 2n$ , where $\sigma(n)$ denotes the sum of the divisors of n. I also revealed that if n is factored into prime powers as $n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_m^{\alpha_m}$ , then $\sigma(n)$ can be calculated as follows:

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

In part II, we saw where this formula actually comes from. Finally, in the challenge interlude, DB and Steve Gilberg (and you?) found that the first four perfect numbers seem to all be of the form $2^k (2^{k+1} - 1)$ ; DB additionally claimed that this only works when $2^{k+1} - 1$ is prime.

Well, it’s true: $2^k (2^{k+1} - 1)$ is perfect whenever $2^{k+1} - 1$ is prime. But you don’t have to take my word for it—let’s prove it! Since n is perfect if $\sigma(n) = 2n$ , we want to show that $\sigma(2^k (2^{k+1} - 1)) = 2^{k+1} (2^{k+1} - 1)$ if $2^{k+1} - 1$ is prime. Applying the formula for $\sigma(n)$ , this is just some straightforward algebra. (Note: by “straightforward” I don’t mean “you’re dumb if you don’t see it immediately”; I mean “if you’re patient and persistent, you should be able to work it out for yourself”. Mathematicians are fond of saying that things are “obvious” or “straightforward”, but this is what they actually mean.)

$\begin{array}{rcl} \sigma(2^k (2^{k+1} - 1)) & = & \frac{2^{k+1} - 1}{2 - 1} \cdot \frac{(2^{k+1} - 1)^2 - 1}{(2^{k+1} - 1) - 1} \\ & = & (2^{k+1} - 1) \cdot \frac{2^{2k+2} - 2^{k+2} + 1 - 1}{2^{k+1} - 2} \\ & = & (2^{k+1} - 1) \cdot \frac{2^{k+1}(2^{k+1} - 2)}{2^{k+1} - 2} \\ & = & (2^{k+1} - 1) \cdot 2^{k+1} \end{array}$

Voila! Just what we wanted to show. Note that the restriction that $2^{k+1} - 1$ must be prime is very important: the formula for $\sigma(n)$ assumes that n is factored as a product of prime powers, so the computation above is invalid if $2^{k+1} - 1$ can be factored further.

So, the question becomes, when is a number of the form $2^m - 1$ prime? Well, first of all, m must be prime; if m can be factored as $m = pq$ , then $2^m - 1$ can also be factored, as $(2^q - 1)(2^{q(p-1)} + 2^{q(p-2)} + \dots + 2^q + 1)$ . But is it enough for m to be prime?

Notice that the first four perfect numbers correspond to the first four primes, 2, 3, 5, and 7:

$\begin{array}{rcl} 6 & = & 2^1 (2^2 - 1) \\ 28 & = & 2^2 (2^3 - 1) \\ 496 & = & 2^4 (2^5 - 1) \\ 8128 & = & 2^6 (2^7 - 1) \end{array}$

The next one, however, dashes our hopes: $2^{11} - 1 = 2047 = 23 \cdot 89$ . Now, it is important to note that this doesn’t necessarily mean that $2^{10} (2^{11} - 1) = 2096128$ isn’t perfect: we have only proven above that $2^k (2^{k+1} - 1)$ is perfect when $2^{k+1} - 1$ is prime, which doesn’t necessarily say anything about what happens when it isn’t. However, it turns out that this is indeed true. In fact, more is true: all even perfect numbers must be of the form $2^k (2^{k+1} - 1)$ , with $2^{k+1} - 1$ prime. There are no other kinds of even perfect numbers. So, we saw that 11 doesn’t give us a perfect number, but it turns out that the next three primes (13, 17, and 19) do:

$\begin{array}{rcl} 2^{12} (2^{13} - 1) & = & 33550336 \\ 2^{16}(2^{17} - 1) & = & 8589869056 \\ 2^{18}(2^{19} - 1) & = & 137438691328 \end{array}$

are all perfect. But then a few more primes get skipped; the next perfect number corresponds to 31.

Primes of the form $2^m - 1$ might ring a bell for long-time readers of this blog: these are the Mersenne primes! As of right now, we know of 44 Mersenne primes, and therefore we know about 44 perfect numbers. The largest known Mersenne prime has almost ten million digits, so the largest known perfect number has about twice that many!

Now, what about odd perfect numbers? Are there any odd numbers which equal the sum of their proper divisors?

…No one knows!!

About Brent

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

View all posts by Brent →

This entry was posted in algebra, number theory, open problems, primes, solutions. Bookmark the permalink.

11 Responses to Perfect numbers, part III

George Bell says:

November 27, 2007 at 7:08 pm

Amazing stuff! I spotted a typo, I think. In your factoring of 2^m-1 I think the first term should be (2^p-1), not (2^p+1).

It would seem that by now, somebody would have proved there are no odd perfect numbers!
George Bell says:

November 27, 2007 at 7:24 pm

… actually, the term above should be (2^q-1)
Jonathan says:

November 27, 2007 at 9:15 pm

Thanks for a nice series. I used a bit of it today. My kids factor fairly well, so the derivation was accessible.

In fact, one of our problems (from last month) was to count factors, which made following your work easier.
Brent says:

November 28, 2007 at 8:38 am

George: Thanks for the typo catch! No matter how carefully I proofread my posts… =) It is pretty incredible that the question of odd perfect numbers remains open. Partly I suppose it’s because the answer seems not to have much practical significance, but partly it’s just a very difficult problem.

Jonathan: Excellent, fun to hear that you used some of this with your kids. I’ve got another series planned that I’m really excited about, which I think your students would also enjoy… =)
Steve Gilberg says:

November 28, 2007 at 10:36 am

We don’t know about odd perfect numbers because positive integers are infinitely many. Someday we might find one, but otherwise the answer can only be that we don’t know.
Brent says:

November 28, 2007 at 11:37 am

Steve: actually, that’s not quite right. Of course, you’re right that since the positive integers are infinite, it’s impossible to ever complete an exhaustive search for odd perfect numbers — in other words, we can never say “there are no odd perfect numbers, because we haven’t found any”. There will always be more positive integers to search.

However, it is possible that someone could logically prove that no odd perfect numbers can possibly exist. For example, in a previous comment I recall that you proved there are no “prime triplets” other than 3,5,7 — we know with logical certainty that such triplets cannot exist, even without doing an exhaustive search. It’s possible that something similar could be done for odd perfect numbers — but so far, no one has been able to.

An interesting, related question is this: if odd perfect numbers do not, in fact, exist, must there exist a proof of this fact? The somewhat surprising answer is “no”, as shown by Gödel in 1931. There exist true things which can’t be proven! But we can never know if the existence of odd perfect numbers is of this sort — somewhat paradoxically, the knowledge that a proof of theorem X does not exist in this sense, would itself be a proof of theorem X! So the best we can do is keep looking for odd perfect numbers or for a proof that they can’t exist.
The reader formerly known as DB says:

November 28, 2007 at 3:58 pm

Brent, I’ll disagree with your statement beginning, “Now, it is important to note…” 2,096,128 certainly has factors 2^10 and (2^11 – 1) (regardless of whether the latter is prime). Therefore, all the terms in the expansion of (1 + 2 + … + 2^10) * (1 + (2^11 – 1)) are factors of 2,096,128, and their sum is already twice 2,096,128. If (2^11 – 1) is not prime, then there are other factors to put in the sum as well, so sigma(n) will certainly be too large.

So when (2^(k+1) – 1) is not prime, I think it is clear that sigma(n) > 2n.
Brent says:

November 30, 2007 at 2:24 pm

DB: That’s a nice way of explaining it, I hadn’t thought about it in that much detail.

I guess the real point I was trying to make was that proving something of the form “if A is true, then B is true” does NOT, in and of itself, mean that “if A is false, then B is false”; you need to argue that separately. Now, in this case, it happens that both hold, as you pointed out with a nice, simple explanation. My point still stands, though: the proof that I gave, *in and of itself*, does not say anything about what happens when (2^(k+1) – 1) is not prime.
Kenny Easwaran says:

December 1, 2007 at 5:44 pm

Just a slight correction on your comment about Gödel – the fact that a statement is undecidable may well be provable, as has been shown about the Continuum Hypothesis and the Axiom of Choice (with respect to Zermelo-Frankel set theory). For simple enough statements, things are slightly more complicated – if the existence of an odd perfect number was shown to be undecidable, then we would know that there are in fact no odd perfect numbers. (If there was such a number, then we could just happen upon it and check that it was odd and perfect, which would contradict the undecidability of the statement.) But we might be able to show that the non-existence is unprovable, without showing that existence was unprovable, so in this case it could be true but not provable, and we would know that it wasn’t provable, though we wouldn’t know that it was true.
Brent says:

December 3, 2007 at 6:01 pm

Kenny: thanks for the correction! I’ve picked up my knowledge of Gödel’s incompleteness theorem from various places (GEB and so on) without ever really formally studying it, so I’m not surprised that my understanding has some technical gaps. But I’m glad to know the full story, so thanks for commenting.
Jose Dris says:

September 11, 2008 at 4:29 pm

Some Conjectures Relating to Odd Perfect Numbers (OPNs)

1. If $N = {p^k}{m^2}$ is an OPN with Euler’s factor $p^k$, then is it true that $p^k < m$? (I have a proof for the case $p^k < m^2$, but is unable to extend the methods used to cover the case $p^k < m$. I am able to prove, however, that $I(p^k) < I(m)$, where $I(x)$ is the abundancy index of $x$. Notice that $gcd(p^k, m) = 1$.)

2. Is it possible to establish a one-to-one correspondence between some subset of the set of rational points on the hyperbolic arc $XY = 2$ and the set of odd perfect numbers, using the notion of abundancy indices and/or outlaws? (I tried the mapping $X = \displaystyle\frac{\sigma(p^k)}{p^k}, Y = \displaystyle\frac{\sigma(m^2)}{m^2}$ (where $p^k$ and $m^2$ are defined as in #1 above) and had shown that (X, Y) is neither surjective nor injective over a specific region.)

3. Is it possible to improve the chain of inequalities $\displaystyle\frac{57}{20} < {\displaystyle\frac{\sigma(p^k)}{p^k} + \displaystyle\frac{\sigma(m^2)}{m^2}} < 3$, where $p^k$ and $m^2$ are as in #1 above? (I ask this because any further improvement(s) to the lower and upper bounds would entail nonexistence of OPNs of certain forms.)