# 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:

'SIEVE OF ERATOSTHENES

```'4/97 PAUL E. BECKER
'CLEAR SPACE FOR PRIME ARRAY
DIM A(10000) AS INTEGER

FOR X = 2 TO 10000
'MARK ENTRY AS UNUSED
A(X) = 0
NEXT X

'PRINT ALL PRIMES UP TO 10000
FOR X = 2 TO 10000
IF A(X) = 0 THEN
'DISPLAY PRIME
PRINT X,
'NOW MARK ALL MULTIPLES OF THIS NUMBER AS BAD
FOR Y = X TO 10000 STEP X