 # ## Perfect Numbers (Mar, 1953)

The list of perfect numbers currently stands at 49 entries.

Perfect Numbers

Six is such a number: it is the sum of all numbers that divide it except itself. In 2,000 years 12 perfect numbers were found; now a computer has discovered five more

by Constance Reid

THE GREEKS, greatly intrigued by the fact that the number 6 is the sum of all its divisors except itself (1+2 + 3), called it a “perfect” number. They wondered how many other such numbers there were. It was easy enough to ascertain by trial that the second perfect number was 28 (1+2 + 4 + 7+14). The great Euclid was able to prove that in all cases where a number can be factored into the form 2^n-l(2^n—1) and 2^n—1 is a prime number, the number must be the sum of all its divisors except itself. Thus in the case of 6, n is 2 and 2^n—1=3, a prime number; in the case of 28, n is 3 and 2^n—1 = 7, again a prime number. With Euclid’s formula it was no difficult matter to compute that the third and fourth perfect numbers were 496 (n=5) and 8,128 (n = 7). But beyond that the computation became laborious, and in any event it was not proved that this rule included all the perfect numbers. Euclid left for future mathematicians a challenging question: How many perfect numbers are there?

In more than 2,000 years mathematicians were able to turn up only 12 numbers that met the strict requirements for numerical perfection. Within the past year, however, the University of California mathematician R. M. Robinson has, with the aid of a modern computer, discovered five more. The discovery did not attract the attention of the press. Perfect numbers are not useful in the construction of atomic bombs. In fact, they are not useful at all. They are merely interesting, and their story is an interesting one.

For many centuries philosophers were more concerned with the ethical or religious significance of perfect numbers than with their mathematics. The Romans attached the number 6 to Venus, because it is the product of the two sexes—the odd (masculine) number 3 and the even (feminine) number 2. The ancient Hebrews explained that God chose to create the world in six days rather than in one because 6 is the more perfect number. The eighth-century English theologian Alcuin pointed out that the second origin of the human race, from the eight human beings on Noah’s Ark, was less perfect than the first, 8 being an imperfect number. In the 12th century Rabbi Josef Ankin recommended the study of perfect numbers in a program for the “healing of souls.”

THE mathematicians, meanwhile, had been making slow progress. The first four perfect numbers—6, 28, 496 and 8,128—had been known as early as the first century. Not until 14 centuries later was the fifth discovered. It was 33,550,336 (n=13). Then in 1644 the French mathematician Marin Mersenne, a colleague of Descartes, announced six more at one clip, and thereby linked his name forever with perfect numbers. The numbers were now so large that they were necessarily described only by the prime number 2^n—1, or, more briefly, by the exponent, n, in Euclid’s formula. The values of n for the 11 perfect numbers, including Mersenne’s six new ones, were 2, 3, 5, 7, 13, 17. 19, 31, 67, 127 and 257. In other words, the largest prime in the series was the enormous number 2^257— 1.

It was obvious to other mathematicians that Mersenne could not have tested for primality all the numbers he had announced. But neither could they. At that time the only method of testing was to try every possible divisor of each number. By this laborious method mathematicians did test Mersenne’s first eight numbers and found them prime.

It was the great Swiss mathematician Leonhard Euler who tested the eighth number (2^31 —1). Euler also proved that all even perfect numbers must be of the form expressed by Euclid’s theorem. No odd perfect number has ever been found, but it has never been proved that such a number cannot exist.

For more than 100 years the perfect number formed from the prime 2^31 — 1 remained the largest proved. Then in 1876 the French mathematician Eduard Lucas worked out a method by which a possible prime could be tested without trying all potential divisors. At the same time he announced that he had tested 2^127—1 by his method and found it prime.

According to Lucas, the number 2^n—1 is prime if, and only if, it divides the (n— 1) term of a certain series. In this series the first number is 4 and each succeeding number is the square of the preceding one minus 2; in other words 4, 14, 194, 37,634, and so on. For example, to test the prime number 7 (2^3—1), one divides 7 into 14; the n—1 term in this case being the second number in the series, since n is 3. Since 7 divides evenly into 14, it is prime by Lucas’ test.

Obviously even Lucas’ short-cut method becomes rather unwieldy when, as in the case of 2^127—1, one must divide 170,141,183,460,469,231,731,687,303,-715,884,105,727 into the 126th term of Lucas’ series. For such numbers, mathematicians use a short-cut of the shortcut: instead of squaring each term of the series, they square only the remainder after they have divided the number being tested into it.

Even with the help of Lucas’ method mathematicians were not able to finish testing all of the possible Mersenne numbers until a few years ago. Their tally showed that Mersenne’s list of perfect numbers was incorrect. He was right on nine numbers (those for which n is 2, 3, 5, 7, 13, 17, 19, 31 and 127), but he was wrong on two he had listed (those with the exponents 67 and 257), and he had missed three numbers in the series (with exponents 61, 89 and 107). Thus the list stood at 12, with 2^126(2^127 —1) the largest known perfect number.

THEN on January 30 last year Robinson fed the problem to the National Bureau of Standards’ Western Automatic Computer, known briefly as SWAC. This is a high-speed machine: it can do an addition of 36 binary digits in 64 millionths of a second. Robinson’s job was to break down the Lucas method into a program of the 13 kinds of commands to which the SWAC responds. The job was complicated by the fact that, while the machine is built to handle numbers up to only 36 binary digits, the numbers he was working with ran to 2,300 such digits. It was, he found, very much like explaining to a human being how to multiply 100-digit numbers on a desk calculator built to handle 10. To tell SWAC how to test a possible prime by the Lucas method, 184 separate commands were necessary. The same program of commands, however, could be used for testing any number of the Mersenne type from 2^3—1 to 2^2297—1.

The program of commands, coded and punched on paper tape, was placed in the machine’s “memory.” All that was then necessary to test the primality of any Mersenne number was to insert the exponent of the new number as it was to be tested. The machine could do the rest, even to typing out the result of the test—continuous zeros if the number was a prime.

The first number to be tested was 2^257—1, the largest of the 11 numbers announced by Mersenne. Twenty years before it had been found not prime by D. H. Lehmer, who worked two hours a day for a year with a desk calculator to do the test. It happened that this evening Lehmer himself, now the director of research at the Bureau of Standards’ Institute for Numerical Analysis on the U.C.L.A. campus, was in the room. He saw the machine do in 48 seconds what had taken him an arduous 700 and some hours. But the machine got exactly the same result.

SWAC then continued on a list of larger possible primes. Mersenne had said that all eternity would not suffice to test whether a given number of 15 or 20 digits was prime. But within a few hours SWAC tested 42 numbers, the smallest of which had more than 80 digits. One by one it determined that they were not prime. Finally at 10 p.m. a string of zeros came up: the machine had found a new perfect number. Its prime was 2^521—1. Just before midnight, 13 more numbers later, another prime came up: 2^607—1. In the decimal system this is a number of 183 digits.

The machine continued testing numbers when opportunity afforded during the next few months. Last June the number 2^1270— 1 was found to be prime. In October, concluding the program, it established as prime the numbers 2^2203 —1 and 2^2281l—1. The latter is the largest prime number, of any form, now known.

The perfect numbers of which these primes are components are, of course, much larger—so large that in comparison with them conventionally “astronomical” numbers seem microscopic. Yet, by a proof as old as Euclid, mathematicians know that these numbers are the sum of all their divisors except themselves—just as surely as they know that 6=1 + 2 + 3.

They still do not know, however, how many perfect numbers there are.

1. Toronto says: November 20, 200910:29 pm

Best computing/math article in a long time, Charlie! Thanks – good picture of the SWAC console, too.

I wonder if we could find the instruction set of that machine – 13 opcodes is an unusual number. I bet it was a “branching” instruction set.

2. Rick Auricchio says: November 21, 20099:15 pm

The Meletron ad makes it appear as if they’ve been able to fix the roulette results.

3. John Savard says: November 21, 20099:28 pm

Some manuals for the SWAC are available for download here (on Al Kossow’s famous computer history site):

http://www.bitsavers.or…