Perfect numbers

One would be hard put to find a set of whole numbers with a more fascinating history and more elegant properties surrounded by greater depths of mystery—and more totally useless—than the perfect numbers.

Martin Gardner, 1997

This entry is dedicated to my beloved wife, Jennifer—for supporting me in my goals, for holding me to my promises, and for putting up with my obsessions.

Let’s take a short hiatus from our program of breaking down already-simple objects into their constituent atoms. Instead we’ll investigate a relatively straightforward question in arithmetic.

A perfect number is a natural number that is the sum of all its divisors aside from itself.

The first perfect number is 6. The divisors of 6 are 1, 2, and 3; and 1+2+3 = 6. This makes it different from a number like, say, 8: the divisors of 8 are 1, 2, and 4, and 1+2+4 = 7 < 8. We say 8 is deficient. A number like 12, on the other hand, for which the sum of the divisors is 1+2+3+4+6 = 16 > 12, is called excessive.

The second perfect number is 28: the sum of its divisors is

1+2+4+7+14 = 28.

The third perfect number is 496:

1+2+4+8+16+31+62+124+248 = 496.

And the fourth is 8128:

1+2+4+8+16+32+64+127+254+508+1016+2032+4064 = 8128.

Now, the perfect numbers were first investigated about 2500 years ago by the Pythagoreans, a sort of mathematical/mystical cult of ancient Greece, and these were the only four known to them. But even with that little data to go on, they began noticing patterns.

One of these patterns is very closely related to the prime numbers. A prime number is a natural number with exactly two divisors: itself and one.  The first seven prime numbers are 2, 3, 5, 7, 11, 13, and 17; and there are infinitely many more where those came from.

What does this have to do with perfect numbers? Well, the first four perfect numbers, as stated above, are 6, 28, 496, and 8128.

  • 6 = 22−1⋅(22−1)
  • 28 = 23−1⋅(23−1)
  • 496 = 25−1⋅(25−1)
  • 8128 = 27−1⋅(27−1)

Pretty neat, huh? Based on this you might guess that the fifth perfect number would be 211−1⋅(211−1), and the sixth would be 213−1⋅(213−1), and so on. In fact, the Pythagoreans guessed exactly that.

Conjecture. The perfect numbers are exactly the numbers of the form 2p−1⋅(2p−1), where p is a prime number.

Once you make a bold conjecture like this, the best thing to do is look for the most immediate possible counterexample. In this case, the thing to ask is: “Is 211−1⋅(211−1) actually a perfect number?”

In the bad old days this would have taken all day to check by hand. But this is the 21st century, so we can just appeal to Wolfram Alpha for help. Asking the right questions allowed me to glean the following information:

  • 211−1⋅(211−1) is also known as 2,096,128.
  • It has 44 divisors, including itself.
  • The sum of the 43 ‘proper’ divisors is 2,210,760, which is greater than 2,096,128.

In other words, 211−1(211−1) is an excessive number.

So much for that conjecture.

Euclid’s fix

So what gives? It can’t just be a coincidence that the first four perfect numbers fall out of that expression. In fact, the fifth perfect number turns out to be 33,550,336, or 213−1(213−1). (This number was first attested in 1436, some two thousand years after the Pythagoreans discovered the first four.) And the sixth is 8,589,869,056, or 217−1(217−1). (This one wasn’t found until 1588.)

Is there just something wrong with the number 11?

Well, it’s not just 11: the next ‘failure’ in this regard is the prime number 23. But yeah, there is something wrong with it.

Let’s look at our expression: 2p−1(2p−1). If we want to know whether a number of this form is perfect, we need to know its divisors. Now, listing the divisors of 2p−1 is easy: it’s a power of 2, so its divisors are precisely the smaller powers of 2. What about the other piece, the 2p−1?

  • When p is 2, that means 2p−1 is 3: a prime number.
  • When p is 3, that means 2p−1 is 7: a prime number.
  • When p is 5, that means 2p−1 is 31: a prime number.
  • When p is 7, that means 2p−1 is 127: a prime number.
  • When p is 11, that means 2p−1 is 2047: not a prime number!

And even if we relax the requirement that p itself be prime, it won’t help. 24−1, 26−1, 28−1, etc. aren’t prime either. In fact, the first six numbers p for which 2p−1 is prime are—guess what?—2, 3, 5, 7, 13, and 17.

It was with this in mind that, around 30 bce, the Alexandrian mathematician Euclid included the following proposition in his treatise The Elements, Book IX.

Proposition 36. If as many numbers as we please beginning from a unit are set out continuously in double proportion until the sum of all becomes prime, and if the sum multiplied into the last makes some number, then the product is perfect.

Euclid didn’t have algebra or the Hindu-Arabic numeral system on his side when he wrote his Elements, so he had to state all his propositions in this wordy way. Let’s translate to a more modern notation.

Theorem. Every natural number of the form 2n−1⋅(2n−1), where 2n−1 is prime, is a perfect number.

Proof. Some divisors of 2n−1⋅(2n−1) are

    • 1, 2, 4, …, 2n−2, and 2n−1 (the divisors of 2n−1);
    • 2n−1, 2⋅(2n−1), 4⋅(2n−1), …, and 2n−2⋅(2n−1) (the divisors of 2n−1, times 2n−1, except for 2n−1⋅(2n−1) itself).

Moreover, if 2n−1 is prime, then these are the only divisors of 2n−1⋅(2n−1). Let’s add them together.

    • 1+2+4+…+2n−1 = 2n−1. (This isn’t hard to prove.)
    • (2n−1)+2⋅(2n−1)+4⋅(2n−1)+…+2n−2⋅(2n−1) = (2n−1−1)(2n−1).
    • (2n−1)+(2n−1−1)(2n−1) = 2n−1(2n−1).

Hooray! The number is perfect.  ∎

This result is pretty cool, but it does leave one question open: why, for the first six perfect numbers, is n prime as well? Fortunately, the answer to that is pretty simple. It turns out that, for 2n−1 to be prime, n must be prime. Specifically, if some number d divides n, then 2d−1 divides 2n−1. (Proving this is a standard exercise in number theory classes.)

A counting question

So, how many perfect numbers are there?

That question may seem kind of dopey now that we have the theorem above. We can use it to produce as many perfect numbers as we want, right?

Well, maybe.

A prime number of form 2n−1 is called a Mersenne prime. We know that for every Mersenne prime, there is a corresponding perfect number. This means that there are at least as many perfect numbers as there are Mersenne primes.

But it turns out that Mersenne primes themselves are pretty rare. Just how rare, you ask? Well, out of the first 1,329,943 prime numbers p—that is, all the prime numbers under 21 million—there are exactly 40 for which 2p−1 is also prime. If you were looking forward to using Mersenne primes to generate umptillions of perfect numbers, you’d better start now.

But no matter how soon you start, you won’t find a new Mersenne prime if you’ve already found them all. Which might lead you to ask:

Question 1. Just how many Mersenne primes are there anyway?

No one in the world knows the answer to this question. In fact, no one even knows whether there are finitely or infinitely many.

Well, let me qualify that statement. Most mathematicians are quite confident that there are infinitely many Mersenne primes, for reasons I don’t pretend to fully understand. But actually proving this conclusively is one of the great open challenges in mathematics, unresolved over two thousand years after Euclid.

A list of all 47 known Mersenne primes is available online, along with a few known facts and theorems about Mersenne primes and perfect numbers. All of the largest known Mersenne primes (indeed, all of the largest known prime numbers) have been discovered by the Great Internet Mersenne Prime Search (GIMPS), a distributed computing project to which anyone can contribute by downloading a client from their website. (Their most recent discovery: the number 242,643,801−1, found to be prime on April 12, 2010.) Nothing is required of you except to leave an unobtrusive program running on your computer, and there are cash prizes available for actually finding a Mersenne prime, so the effort is worth joining.

Things get odd

If there are only finitely many Mersenne primes, then our perfect number generator will eventually peter out. But this doesn’t necessarily mean there are only finitely many perfect numbers. To know that, we need the answer to a second question.

Question 2. Are there any perfect numbers that are not of form 2n−1⋅(2n−1)?

The 18th century mathematician Leonhard Euler found a partial negative answer to this question: all even perfect numbers are of form 2n−1⋅(2n−1). Several proofs, including Euler’s own, can be found in John Voight’s Perfect Numbers: An Elementary Introduction. This simplifies the question somewhat.

Question 2 (revised). Are there any odd perfect numbers?

This, along with the infinitude of Mersenne primes (and of perfect numbers themselves), is a serious contender for the the oldest open question in mathematics, having been asserted true without proof by Nicomachus of Gerasa as early as the second century. As with Question 1, no one in the world knows the answer.

And as with Question 1, I’ll have to qualify that. Most mathematicians are very confident that the answer is no. All the odd numbers with 300 digits or fewer have been known for some time not to be perfect, and the website OddPerfect.org now claims completion of a search up to 1250 digits. It’s also known that, if there is an odd perfect number, its largest prime divisor must be greater than 100,000,000. In 1888, James Joseph Sylvester published a series of papers in the journal Comptes Rendus,  detailing these and many other rare and elaborate conditions that an odd number would have to satisfy in order to have a chance of being perfect. He finally concluded,

…a prolonged meditation on the subject has satisfied me that the existence of any one such — its escape, so to say, from the complex web of conditions which hem it in on all sides — would be little short of a miracle.

I don’t deny that this sort of heuristic argument has its merits. At the very least, even if an odd perfect number exists, it tells us that we’re unlikely ever to stumble across one. And I’m no number theorist, so my thoughts don’t have huge weight here. But my own underinformed opinion is that Sylvester’s case is not very strong.

At best, a “complex web of conditions” like Sylvester’s can offer an upper bound on the probability that any specific odd number is perfect. But if we expect that no odd number is perfect, that probability must be exactly 0. If it’s merely very, very small—on the order of one in 3↑↑↑↑3, say—then eventually, somewhere in the infinitude of the natural numbers, odd perfect numbers must occur.

Which isn’t to say I disagree with the consensus. In all likelihood it’s true that there are no odd perfect numbers. There are better arguments than Sylvester’s available today, such as Pomerance’s heuristic, which make it seem like such a thing really would be a miracle. But I haven’t heard of any serious progress toward a proof of non-existence.

There are some folks searching for odd perfect numbers, notably those at OddPerfect.org, but to my knowledge there is nothing like the focused, distributed, worldwide effort that is GIMPS. No one is offering $3000 cold cash to the discoverer of an odd perfect number. And yet if one were found, it would rank among the greatest upsets in the history of mathematics. The clean correspondence between perfect numbers and Mersenne primes would be broken. The problem of classifying the perfect numbers, thought essentially solved, would turn out to be more tortuous than anyone had suspected. Every number theorist in the world would greet the impossible number with shock and awe, and the brilliant (or lucky) discoverer would be immortalized.

Despite this, I don’t recommend you spend your time searching for odd perfect numbers, for the same reason that I don’t recommend you spend your time searching for Bigfoot. Might such a creature exist? Sure, maybe. Does such a creature exist? Probably not. If it does exist, are you uniquely qualified to find it? I wouldn’t bet on it. Do you want to dedicate your life to being “that Bigfoot guy” while bigger questions, to which you could have made great contributions, remain unanswered? I’ll leave that up to you.

Advertisements

4 responses to “Perfect numbers

  1. niiiiiiiiiiiiiiiiiiiiice. thanks for the article ^_^

  2. Great article! Looking forward to more such enlightening posts! 🙂

    • Wow, someone is still reading this? I was still feeling vaguely guilty about not having updated in a while… but if I still have actual readers I may have to stop just feeling guilty and do something about it.

      New post later this week!

  3. Perfect numbers, whether odd or even, have a single multiplicative form:

    EPN = 2^{p – 1}{2^p – 1} = “Prime power with even exponent” x “Large prime with exponent 1”
    OPN = {m^2}{q^k} = “Composite power with even exponent” x “Special prime power”

    The “special prime power” is also called the “Euler prime component” of the OPN. Ronald Sorli conjectured in 2003 that k is actually 1 (i.e. q || N, if N is an OPN). Sorli made this conjecture on the basis of some numerical evidence generated by the computer-assisted attempt to prove that omega(N) is at least 9. (Note: omega(N) is the number of distinct prime factors of N.)

    I have a paper (to appear) that lists some sufficient conditions for Sorli’s Conjecture. You may view the preprint online at http://arxiv.org/abs/1103.1090.

    Just let me know if you’re interested to know more.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s