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:
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.
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 NOT ALREADY MARKED BAD, USE IT
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
'MARK IT BAD
A(Y) = 1
NEXT Y
END IF
NEXT X
END
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.