lilpleth.gif (2419 bytes)

Perfect Numbers

by Paul Becker
updated September, 1999 with newly discovered perfects

     Since the beginning, mathematicians have assigned mystical, magical, and even sacred properties to numbers.  In the days of the Greeks, one such set of numbers were the perfects.  A "perfect" number is a whole number that equals the sum of its divisors (except itself).  Six is the first perfect, because 1,2, and 3 are factors, and 1+2+3 = 6.  The next perfect is 28 (1,2,4,7,14).  Early Christian and Jewish observers noted the obvious perfection of 6 and 28, for the Earth was created in six days and the moon circles the Earth every 28.  In fact, St. Augustine argued that "Six is a number perfect in itself, and not because God created all things in six days; rather the inverse is true; God created all things in six days because the number is perfect.  And it would remain perfect even if the work of the six days did not exist."  (The City of God, Book 11, Chapter 30).  The "perfection" seemingly ends here, because the next two perfects are 496 and 8128.

     With these four perfects; 6, 28, 496, 8128; the ancients made observations that:

  1. Perfect numbers end in either six or eight.
  2. Perfect numbers are even.
  3. The ending number would alternate between six and eight.
  4. The first perfect has one digit, the second has two, the third three, the fourth four, so the fifth must have five.

     Well, they weren't exactly right...all known perfects do end in either 6 or 8, but unfortunately, there isn't a recognizable pattern.  As far as observation two goes, well, nobody can prove it yet.  Observation four is even more of a letdown, because the fifth perfect is eight digits: 33,550,336 - and they go skyward in size from there - more on that later, but for now, more fascinating history:

     Euclid and the Prime Number Connection  In Euclid's day, these four perfects were all that were known.  Incredibly, he saw that for each of these perfects, the formula 2n - 1(2n - 1) produces perfects for the prime n values of 2, 3, 5, 7.  Example:

For n=2, 21(22 - 1) = 2(3) = 6.

Notice that 2n-1 is also prime.  Euclid (brilliantly?) proved that 2n - 1 (2n - 1) yields an even perfect number when 2n - 1 is a prime number.  Note also that not all primes work for n to yield a perfect.

In the 1700's, Euler expanded on Euclid's formula and proved that it will yield all of the even perfect numbers.

     Mersenne Primes.  Today, numbers generated by the expression 2n - 1 are known as Mersenne numbers, named after Marin Mersenne, a monk, scholar, and generally cool guy.  If the number generated happens to be prime, it is known as a Mersenne prime.  Thanks to Euclid, you can use that Mersenne prime to automatically find a perfect number.  In fact, when a new Mersenne prime is discovered, you can be sure I'm having a good day.  I'm looking for the next Mersenne Prime during spare CPU cycles on my computer.  You can too!  See the link at the top of this page.

     Oh, by the way, Mersenne was no slouch either.  In 1644, he boldly proclaimed that the Mersenne numbers 213 - 1, 217 - 1, and 219-1 are all prime.  He was right!

     The known perfects:  Because the perfects get huge fast, I'll give you n, where n plugs into the expression  2n - 1(2n - 1) to yield the perfect.  The actual computation is left to you!  Although 36, 37 and 38 are listed, there may be other perfects in between them that have not yet been discovered.

  1. 2
  2. 3
  3. 5
  4. 7
  5. 13
  6. 17
  7. 19
  8. 31
  9. 61
  10. 89
  11. 107
  12. 127
  13. 521
  14. 607
  15. 1279
  16. 2203
  17. 2281
  18. 3217
  19. 4253
  20. 4423
  21. 9689
  22. 9941
  23. 11213
  24. 19937
  25. 21701
  26. 23209
  27. 44497
  28. 86243
  29. 110503
  30. 132049
  31. 216091
  32. 756839
  33. 859433
  34. 1257787
  35. 1398269
  36. 2976221
  37. 3021377
  38. 6972593

     I gotta get me some primes!  Now, if you only had a source of primes, you could make a "possible perfect" generating program.  Remember that Euclid's formula doesn't work for every prime, so you have to factor each number you get out of it to see if it is perfect.  So where do you get this stream of primes?  Here's one possibility:

     The Sieve of Eratosthenes.  The sieve algorithm can be used to find prime numbers rather quickly.  The algorithm is simple:  Make a list of numbers, starting with two and incrementing by one; for example:

2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17, and so on.

     Two is the first prime, but you know that every other multiple of two is not, so cross them out, leaving:

2,3,5,7,9,11,13,15,17, and so on.

     Since three is not a multiple of two, it is prime, so now cross out every other multiple of three, leaving:

2,3,5,7,11,13,17, and so on.

     Five is not a multiple of 2 or 3, so it is prime.  Cross out every multiple of 5 remaining.

     By now, you get the picture.  This algorithm starts out slowly, but gets to the point rather quickly.  Try it:



FOR X = 2 TO 10000
  A(X) = 0

FOR X = 2 TO 10000
  IF A(X) = 0 THEN
    PRINT X,
    FOR Y = X TO 10000 STEP X
      'MARK IT BAD
      A(Y) = 1
    NEXT Y

     It doesn't take much imagination to realize that you could take the resultant primes and plug them into Euclid's algorithm, factor the number yielded, add the factors (except for the number itself, remember?) and identify perfects.  This is the method I used, but there's just one thing missing...  The numbers get huge FAST, and how on Earth do you factor such numbers?

     We'll cross that bridge in part two.  

     Sidenote for those who care:  I've been involved in "perfect hunting" since about 1986, when Professor Kathy Rust assigned a "brute force" perfect number hunting program in a FORTRAN class.  At first, my program simply factored numbers sequentially and added the factors.  Simple.  If the sum of the factors (excluding one) didn't equal the target, go on to the next number.

     Since completing that assignment, I have been fascinated by perfect numbers and developing faster methods for their discovery on an ordinary home computer.  This article series chronicles my adventure into Very Large Numbers.