perfect number

An integer which is equal to the sum of its positive divisors. The first three are:
6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
It is unknown if there are any odd perfect numbers. Many cultures throughout history have ascribed religious and mystical significance to these numbers.

Some facts about perfect numbers:

• Even perfect numbers end in either six or eight.
• Perfect numbers are even...so far.
• There are infinitely many perfect numbers.
• If there are odd perfect numbers, they at least are bigger than 10^300.

List of known perfect numbers:

1. 6
2. 28
3. 496
4. 8,128
5. 33,550,336
6. 8,589,869,056
7. 137,438,691,328
8. 2,305,843,008,139,952,128
9. 2.658x10^36
10. 1.916x10^53
11. 1.316x10^64
12. 1.447x10^76
13. 2.356x10^313
14. 1.411x10^365
15. 5.416x10^769
16. 1.089x10^1326
17. 9.950x10^1372
18. 3.357x10^1936
19. 1.820x10^2560
20. 4.077x10^2662
21. 1.143x10^5833
22. 6.000x10^5984
23. 3.960x10^6750
24. 9.311x10^12002
25. 1.007x10^13065
26. 8.115x10^13972
27. 3.651x10^26789
28. 1.441x10^51923
29. 1.362x10^66529
30. 1.315x10^79501
31. 2.783x10^130099
32. 1.516x10^455662
33. 8.385x10^517429
34. 8.497x10^757262
35. 3.319x10^841841
36. 1.943x10^1791863
37. 8.117x10^1819049

Any even perfect number a is of the form a = 2^n-1(2ⁿ-1), where 2ⁿ-1 is a prime number. While it is difficult to prove that all perfect numbers have this form, it is not very difficult to prove that these numbers are indeed perfect:
The divisors of a are 1, 2, 2², ..., 2^n-1, and (2ⁿ-1), 2*(2ⁿ-1), 2²(2ⁿ-1), ..., 2^n-2(2ⁿ-1). The sum of the divisors not containg the (2ⁿ-1) factor is 2ⁿ-1, and the sum of the other divisors is (2^n-1-1)(2ⁿ-1). Grand total: 2^n-1(2ⁿ-1) = a. Thus a is perfect.

Most formally, a perfect number is a natural number n for which σ(n) = 2n. The σ function (lowercase sigma, for those without σ in their browser's character set) returns the sum of the aliquot parts of a number, aka the sum of all the number's divisors (all divisors, not just the proper ones). If σ(n) < 2n, then n is called deficient. If σ(n) > 2n, then n is called abundant.

There has been some interest lately in finding "multiple perfect numbers," numbers for which σ(n) = kn, for integers k greater than 2. The human race has yet to discover a multiple perfect number with k = 11, although many have been discovered for k = 10.

Mathematics has a dirty secret: Like many other disciplines, it had its foundations in pseudoscience, in this case numerology. Certainly people had begun to count and measure and weigh things, but you couldn't have called counting and weighing and measuring "mathematics" until someone started searching for abstract properties of numbers. And it seems to be a constant in human history for the abstract to begin with the mystical.

One of the earliest groups of people using numbers for mumbo-jumbo was a school of ancient Greeks founded by the legendary Pythagoras. The Pythagoreans noticed that when the divisors ("parts") of certain numbers were added up, the result was the original number. For example:

6 = 1 + 2 + 3

28 = 1 + 2 + 4 + 7 + 14

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

In modern notation we would say

σ₀ (N) = N

(The subscripted zero will be explained momentarily.)

By the time of Euclid the perfection of 6, 28, 496, and probably 8128 were known. Here, we should point out:

6 = 2*3 = 2¹*(2²-1)

28 = 4*7 = 2²*(2³-1)

496 = 16*31 = 2⁴*(2⁵-1)

8128 = 64*127 = 2⁶*(2⁷-1)

but this is not true for 120 = 8*15 = 2³*(2⁴-1) ; the sum of its divisors is 240.

In the Elements¹, Euclid was able to prove (Book IX, Proposition 76):

If as many numbers as we please beginning from a unit be set out continuously in double proportion, until the sum of all becomes a prime, and if the sum multiplied into the last make some number, the product will be perfect.

That is,

2^k-1(2^k - 1)

is perfect whenever k > 1 and 2^k - 1 is prime. Euclid's proof is a geometric one so we'll omit it. A slighly more comprehensible algebraic one will be demonstrated later.

Perfect numbers were studied by two mathematicians from the First and Second Centuries, Theon of Smyrna and Nichomachus of Gerasa. In his Introduction to Arithmetic Nichomachus classified numbers based upon whether the sum of their aliquot parts² was less than the number, (deficient), greater than the number, (abundant), or equal to the number (perfect). Unfortunately, Nichomachus also made some false assertions about perfect numbers. In addition, Nichomachus injected a bit of mysticism, assigning deficient numbers to objects and concepts with incomplete, corrupt, or inadequate qualities.

Saint Augustine later injects a bit of his own mumbo-jumbo, asserting that God created the earth in 6 days because 6 is a perfect number. The Moon goes through a cycle of phases in 28 days. 666 is deficient. I'm sure he thought he was unlocking something meaningful.

Arabic mathematicians picked up where the Greeks and Romans left off. Thabit ibn Qurra wrote about amicable numbers, pairs of numbers whose aliquot parts add up to each other, and proposed a formula for generating them. Abu Ali al-Hasan ibn al-Haytham was able to restrict the conditions for even perfect numbers.

8191 = 2¹³-1 was found to be prime by the Arabs and by Renaissance mathematicians on two later occasions, yielding the next perfect number, 33550336. Pietro Antonio Cataldi showed that 131071 (that is, 2¹⁷- 1) is prime, yielding the next perfect number, 8589869056. Cataldi also showed 524287 = 2¹⁹ - 1 was prime, yielding another perfect number, 137438691328.

The correspondence of a French monk named Marin Mersenne became a seventeenth-century form of Lexis-Nexis. Mersenne became interested in multiply perfect numbers, that is, numbers where σ₀ (N) = kN where k is some number greater than 1. Mersenne got Rene Descartes so interested in them that the latter discovered a formula for generating multiply perfect numbers and a long list of such numbers.

Another of Mersenne's correspondents was Pierre de Fermat, whose investigations into perfect numbers yielded the first non brute force primality test, Fermat's Little Theorem. With this step, it became easier to show whether a number of the form 2^k-1 was a Mersenne Prime or not.

Leonhard Euler figures into this story, as he figures into nearly everything else mathematical. In 1732, Euler found the next perfect number, 2305843008139952128 (2³⁰(2³¹ - 1)). Euler also appears to be the first person to give us a way to calculate the sum of a numbers divisors without enumerating them and summing them up. It turns out that this is easier if we include the number itself as a divisor, and Euler's sigma function σ(N) calculates the sum of all divisors of N; we get the classical sum by defining

σ₀(N) = σ(N) - N.

Derivation of the sigma function starts by noting that the only divisors of a power of a prime are the number and lower powers of the prime:

σ(p^k) = 1 + p + p²+ ... + p^k

This can be algebraically transformed into the briefer

σ(p^k) = (p^k+1-1)/(p-1)

but keep the longer form in mind because it's important for our later discussion. For a prime p, σ(p) = p + 1. Also, σ(2^k) = 2^k+1-1

Euler also proved that that

σ(ab)=σ(a)σ(b)

whenever a and b are relatively prime. Thus, given a number's unique prime factorization,

N=Πp_i^α_i

it's easy to show

σ₀ (N) = N

means

σ (N) = 2N

Now, we can prove Euclid's last proposition algebraically. For N=2^k-1(2^k - 1), where 2^k-1 is prime,

σ(N) = σ(2^k-1)σ(2^k - 1) = (2^k-1) 2^k = 2N.

Euler was able to improve on the results of Euclid and ibn al-Haytham, proving that all even perfect numbers are of the form given by Euclid. If N=2^k-1q where k > 1,

σ(N) = (2^k-1) σ(q) = 2N = 2^kq

(2^k-1) σ(q) = 2^kq

(2^k-1) σ₀(q) = q

σ₀(q), the sum of all proper divisors of q, is itself a proper divisor of q, meaning the only possible value for σ₀(q) is 1. Therefore, q = 2^k-1 is prime.

The finding of Mersenne primes has become one way for supercomputer manufacturers to show off the capabilities of their new hardware, diving a race to find new ones. As of this writing, there are 42 known Mersenne primes (the highest being 2^25964951-1) and thus 42 known perfect numbers.

---

Odd perfect numbers

In short: Although it hasn't been proven, there probably aren't any. Why is this? If we look at the formula for the sigma function, we notice that σ(p^k) cannot be divisible by p. But σ (N) must be divisible by p_i^α_i for all i. Whenever α_i > 0, all of those p_i factors have to come from σ (p_j^α_j) for some other prime p_j. In effect, it becomes a pigeonholing or rearrangement problem.

The easiest factor to get rid of is the 2 in σ(N) = 2N. σ(p^m) for odd p and odd m is invariably even. But since N is odd, we're allowed only one factor of 2. Thus, one and only one odd prime must have an odd exponent in N's prime factorization. Furthermore, since σ((4n-1)^k) and σ((2m+1)^4j-1) are always divisible by 4, this factor must be of the form (4n+1)⁴ⁱ⁺¹. Since all other primes must have an even exponent in N's prime factorization, this yields another result of Euler's³, namely that any odd perfect number must be of the form

N = (4n+1)Q²

for some odd number Q.

But prime factorizations for the values of σ(p^2k) often involve higher prime factors than p:

σ(3²) = 13

σ(5²) = 31

σ(7²) = 57 = 3 * 19

σ(11⁸) = 235794769 = 7 * 19 * 1772893

σ(83⁴) = 48037081 (prime)

Generating a perfect (or even multiply perfect) number is a feat similar to slaying the Lernean Hydra: Each power of a prime factor generates more prime factors that must be accounted for.

However, some factors generate lower primes all by themselves:

σ(163²) = 26733 = 3 * 7 * 19 * 67

And odd powers often generate heavily factorizable numbers (but remember you can only have one):

σ(37⁵) = 71270178 = 2 * 3 * 7 * 19 * 31 * 43 * 67

There is still the possibility that some immense complex of odd prime factors⁴ that somehow fits together will be found, but I'm not going to hold my breath.

In the supplement to his book Number Theory and its History⁵, Oystein Ore notes several "recent numerical results", including the finding of new Mersenne Primes by computer. In the same note he mentions his own conjecture, involving the harmonic mean of a number's divisors:

H(N) = 1/n * (1 / d₁ + 1 / d₂ + ... ) = N*ν(N)/σ(N)

where ν(N) is the number of divisors of N, which can be calculated as Π(1+α_i) where α_i is the exponent of a given prime p_i in N's prime factorization. For perfect numbers and a few rare others, H(N) is an integer⁶, and all of these numbers are even. But this doesn't seem to get us very far, since it amounts to the same rearrangement problem we have above.

---

¹Euclid: The Thirteen books of The Elements: Vol 2 (Books III-IX), translated with introduction and commentary by Sir Thomas L. Heath, Dover, New York, 1956. ISBN 0-486-60089-0

²At first glance, the word aliquot seems like it has an Arabic derivation, but is in fact Latin, meaning "some" or "several".

³I was at least able to derive something myself, before finding out through MathWorld that Euler had already done it.

⁴Might such a complex form a finite field?

⁵Oystein Ore, Number Theory and its History Dover, New York, 1948, rev. 1988 (ISBN 0-486-65620-9).
References to this book pervade the writeup. Get it. Read it.

⁶Proof that ν(N) is even when N is a perfect number is left as an exercise for the reader.

Information on Roman, Arab, and Renaissance efforts regarding perfect numbers came from
University of St. Andrews, MacTutor
http://www-history.mcs.st-andrews.ac.uk/history/HistTopics/Perfect_numbers.html