Perfect Numbers

Dr. Math FAQ || Classic Problems || Formulas || Search Dr. Math || Dr. Math Home

#### What is a perfect number? How do you find them? How many are there?

A contribution from John Knoderer, the MazeMan:

1. What is a perfect number?

A perfect number is a whole number, an integer greater than zero; and

when you add up all of the factors less than that number, you get that number.

Examples:

The factors of 6 are 1, 2, 3 and 6.
1 + 2 + 3 = 6

The factors of 28 are 1, 2, 4, 7, 14 and 28.
1 + 2 + 4 + 7 + 14 = 28

The factors of 496 are 1, 2, 4, 8, 16, 31, 62, 124, 248 and 496.
1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 = 496

The factors of 8128 are 1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 1016, 2032, 4064 and 8128. I'll let you add them up.

According to The Merriam-Webster Dictionary, the term was first used in the fourteenth century. The Grolier Multimedia Encyclopedia says that perfect numbers are "another example of Greek progress in number theory," and credits the Pythagoreans for coining the term "perfect." If you are interested in learning more about "perfect" numbers, you should also read up about "Mersenne" prime numbers because they are closely related.

The first four perfect numbers were known over 2,000 years ago. Some ancient cultures gave mystic interpretations to numbers that they thought were magic.

I love challenges, so I wrote a program to use trial-and-error, starting at 1 and trying every whole number going up, looking for perfect numbers. As it ran, I eventually noticed that every perfect number had a higher power of two than the prior number, so I made on-the-fly changes so that the computer would try only multiples of higher powers of two. I eventually found a total of five numbers by this trial and error method. That program eventually ran past a billion before I aborted it.

6 = 1+2+3
28 = 1+2+4+7+14
496 = 1+2+4+8+16+31+62+124+248
8,128 = 1+2+4+8+16+32+64+127+254+508+1016+2032+4064
33,550,336 = 1+2+4+8+16+32+64+128+256+512+1024+2048+4096
+8191+16382+32764+65528+131056+262112+524224
+1048448+2096896+4193792+8387584+16775168

Do you see a pattern in the above numbers? There are all of the powers of 2 from 1 up to a certain number, and then a prime number that is equal to DOUBLE the last power of two, minus 1.

1, 2 ------> 2*2-1 = 3
1, 2, 4 ------> 4*2-1 = 7
1, 2, 4, 8, 16 ------> 16*2-1 = 31
1, 2, 4, 8, 16, 32, 64 ------> 64*2-1=127
1,2,4,8,16,32,64,128,256,512,1024,2048,4096 ------> 4096*2-1 = 8191

The rest of the factors are each power of two TIMES that prime number.

So, our first five perfect numbers are

2 * 3 = 6
4 * 7 = 28
16 * 31 = 496
64 * 127 = 8,128
4096 * 8191 = 33,550,336

Can we turn this pattern of

(Power of Two) * (Double that Power - 1)

into a formula? Yes, we can. Let's call the prime number (2^n-1). In the above examples, we'd have (2^2-1), (2^3-1), (2^5-1), (2^7-1), and (2^13-1). This would make the other number 2^(n-1), or 2^1, 2^2, 2^4, 2^6, and 2^12.

Our formula then would be

Perfect Number = 2^(n-1) * (2^n - 1)

After reading up on how known perfect numbers relate to Mersenne Prime Numbers, I wrote another program, this time to find Mersenne prime numbers and perfect numbers. This program found eight numbers, the five above and three new numbers, which I am not going to factor.

(2^16) * (2^17 - 1) = 8,589,869,056
(2^18) * (2^19 - 1) = 137,438,691,328
(2^30) * (2^31 - 1) = 2,305,843,008,139,952,128

The two programs that I wrote are included at the end of this page.

2. How many perfect numbers are there?

We do not know how many perfect numbers there are. We do know that there are an infinite number of prime numbers, which means there is a very high chance that there are an infinite number of perfect numbers. This is because there is a strong link between perfect numbers and a certain kind of prime number (the Mersenne primes).

3. How many perfect numbers are known?

So far, according to the Mersenne organization, there are 37 known Mersenne prime numbers. This means that there are 37 known "perfect" numbers. The newest prime number was discovered on January 27, 1998. You should always be able to find the most recent information on the Internet at:

Obviously, this is not all of them. There are many that we will never know. We don't even know if the 37th number found is the 37th number; there may be another perfect number between the 35th and the 36th. It is very likely, too, that there are many more that we will NEVER know.

4. Are there any odd perfect numbers?

Nobody has found any odd perfect numbers, but we do not know if any odd ones exist. If any odd perfect numbers exist, they are not based on the "Mersenne" method of calculating perfect numbers. (I hope that we find one someday, but I'm not holding my breath.

5. Where can I find all known perfect numbers?

You can find a listing of all the known perfect numbers on one of the Mersenne Organization's Web pages. You won't see the actual numbers, but you will see the formula and the exponents.

All of the perfect numbers that have been found so far fit the formula

2^(n-1) * ( 2^n - 1 )

where "n" is one of a very short list of prime numbers that can be used to create "Mersenne" prime numbers. You will notice that the eight numbers I found match this formula:

2^1 * ( 2^2 - 1 ) = 2 * 3 = 6
2^2 * ( 2^3 - 1 ) = 4 * 7 = 28
2^4 * ( 2^5 - 1 ) = 16 * 31 = 496
2^6 * ( 2^7 - 1 ) = 64 * 127 = 8,128
2^12 * (2^13-1) = 4096 * 8191 = 33,550,336
2^16 * (2^17-1) = 65536 * 131071 = 8,589,869,056
2^18 * (2^19-1) = 262144 * 524287 = 137,438,691,328
2^30 * (2^31-1) = 1073741824*2147483647=2,305,843,008,139,952,128

The first 35 perfect numbers fit this same formula with "n" values of:

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607,
1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213,
19937, 21701, 23209, 44497, 86243, 110503, 132049,
216091, 756839, 859433, 1257787, and 1398269.

The first eight are calculated and shown above. I leave the rest for you to calculate as an exercise in futility (just teasing).

Another perfect number that has been found is equal to

2^2976220 * (2^2976221-1)

If you multiplied this number out, you would have a number 1,791,864 digits long. We do not know if this would be the 36th, 37th, 38th or ??th perfect number. Since that discovery 2^3021376 * (2^3021377-1) has been found. Eventually, this record will be broken with an even larger number - and you could even be part of the team searching for that number).

As mentioned above, you can find a full list of the exponents for all known "Perfect" numbers, along with the length of each perfect number, the year it was found, and who found it at:

It is interesting to see that some of these numbers were not discovered in order. The ninth, tenth, and eleventh perfect numbers were found after the twelfth was discovered. The 29th was found five years after the 30th and three years after the 31st.

Even students can find these numbers. Two of these numbers, the 25th and 26th, were found by two high school students in 1978 and 1979. They used a university computer to do the work. Students with powerful home computers are invited to join the search, as detailed below.

6. What is a Mersenne Prime Number?

A Mersenne Number is a number that is equal to one less than a power of 2, or (2^n-1) where n is any positive integer. Mersenne numbers are named after Marin Mersenne, a French monk.

A Mersenne Prime Number is a prime number that happens to also be a Mersenne Number. A Mersenne Prime Number will always have a value equal to (2^n-1) where n is one of a selected list of positive prime numbers.

When I discovered that there was a formula for "Mersenne" prime numbers, I wrote another program for that, which gave me these results and is listed later on this page:

2^2-1 = 3
2^3-1 = 7
2^5-1 = 31
2^7-1 = 127
2^13-1 = 8191
2^17-1 = 131,071
2^19-1 = 524,287
2^31-1 = 2,147,483,647

As mentioned above, every known "perfect number" can be generated from a "Mersenne prime". If (2^n-1) describes a "Mersenne prime," then the matching "perfect number" is equal to:

2 ^ (n-1) * ( 2^n - 1)

where n = 2, 3, 5, 7, 13, 17, 19, 31 or other "mersenne" exponents. All of the known "Mersenne" exponents are listed in one of the sections above.

Can we prove that every "Mersenne Prime Number" can generate a corresponding Perfect number? Yes, we can.

Can we prove that every possible "perfect" number can be generated from a "Mersenne" prime? No, we cannot. (I'm hoping that someday someone will find an ODD "perfect" number, and an odd "perfect" number can NOT come from a "Mersenne" prime.)

7. How can you calculate a perfect number from a Mersenne prime?

Let's prove that you can calculate a "perfect" number from every "Mersenne" prime.

If "P" is prime, and it is equal to (2^n-1), then what are the factors of

2^(n-1) * (2^n - 1)    or    2^(n-1) * P       ?

First, let's list the factors of 2^(n-1)

1, 2, 4, 8, 16, 32, 64, 128 ... up to 2^(n-3), 2^(n-2) and 2^(n-1)

The rest of the factors of the perfect number 2^(n-1) * (2^n -1) are each of the above factors multiplied by the prime 2^(n-1). Here's a list of the factors of 2^(n-1) in one column, and the rest of the factors of the perfect number in the second column.

1     1*(2^n-1)
2     2*(2^n-1)
4     4*(2^n-1)
8     8*(2^n-1)
:      :
:      :
:      :
2^(n-3)     2^(n-3) * (2^n-1)
2^(n-2)     2^(n-2) * (2^n-1)
2^(n-1)     2^(n-1) * (2^n-1)

Now, let's add up the left column and see what we get. What is the sum of

1+2+4+8+16+ ... + 2^(n-3) + 2^(n-2) + 2^(n-1)       ?

What do you know? The sum of these numbers is 2^n - 1. Try it on a few powers of 2:

1 + 2 = 3 (2^2 - 1)
1 + 2 + 4 = 7 (2^3 - 1)
1+2+4+8+16=31 (2^5-1)
1+2+4+8+16+32+64=127 (2^7-1)

What is the sum of the other column? We can use the distributive property to add up the numbers. I'll use P as a shortcut for the prime number. Remember, we don't add the last one: that's the number itself, which we don't add when we add up the factors for the perfect number.

1P + 2P + 4P + 8P + 16P + ... + 2^(n-2) P

is equal to

P [ 1+2+4+8+16+ ... + 2^(n-2) ]

We have already determined that (1+2+4+ ... + 2^(n-1) ) is equal to (2^n - 1).

1+2+4+8+16+ ... + 2^(n-2) adds up to 2^(n-1) - 1

So, the left column adds up to 1 * (2^n - 1) and
the right column adds up to [2^(n-1)-1] * (2^n - 1).
```Add:                   1   * (2^n - 1)
+ [ 2^(n-1) - 1 ] * (2^n - 1)
----------------------------------
[ 2^(n-1) ] * (2^n - 1)
```
What do you know? That's the perfect number we started with. So we can see that

2 ^ (n-1) * ( 2^n - 1 )

will always be a perfect number whenever (2^n - 1) is a prime number.

8. How can a computer find perfect numbers?

Here is the program that I used to calculate the first five perfect numbers that I found. This is the slow version that tests every possible number. Once I observed that each succeeding number had more powers of two, I started checking only multiples of succeeding powers of two. That logic is not included here, because it could theoretically let you miss a number (even though it didn't).

```  DEFLNG A-S: m = 0: n = 0: l = 1: q = 0: s = 0: p = 1000: CLS
1 l = l + 1: m = 1: s = 1: q = INT(SQR(l + .5)) + 1
IF l = p THEN LOCATE 25, 1: PRINT l; : p = p + 1000
2 m = m + 1: IF m = q THEN 3
n = l \ m: IF n * m <> l THEN 2
IF s > l - m THEN 1
s = s + m
IF n <> m THEN IF s > l - n THEN 1 ELSE s = s + n: GOTO 2
3 IF s <> l THEN 1
LOCATE 24, 1: PRINT l; "= 1"; : m = 1
4 m = m + 1: IF m = q THEN 5
n = l \ m: IF n * m <> l THEN 4
PRINT "+"; LTRIM\$(STR\$(m)); : GOTO 4
5 m = m - 1: IF m = 1 THEN PRINT : GOTO 1
n = l \ m: IF n * m <> l THEN 5
IF n > m THEN PRINT "+"; LTRIM\$(STR\$(n));
GOTO 5

```
Don't try to type the program. Copy and paste it into a new file, and then load that file into your BASIC compiler or interpreter. I wrote this program in Quick BASIC (extended 7.1). It should run as is in any dos-based BASIC that does not require line numbers on every line. Please have fun optimizing the program to run slightly faster.

Here's the program that I used to generate the first eight "Mersenne" prime numbers and their associated "Perfect" numbers. It runs very quickly. I had to cheat to make the last perfect number display in regular form. BASIC automatically switched into scientific notation when the number got that big.

```  DEFDBL A-Y: DEFSTR Z: CLS
mer = 1: two# = 1: power = 1: xm = y: x2 = y
1 power = power + 1: mer = mer + mer + 1: two# = two# + two#
LOCATE 25, 1: PRINT "Testing"; mer;
FOR i = 3 TO INT(SQR(mer + 1)) STEP 2: IF (mer MOD i) = 0 THEN 1
NEXT
LOCATE 24, 1: PRINT USING "#,###########"; mer;
PRINT " = 2^"; LTRIM\$(STR\$(power)); "-1";
IF power < 31 THEN
PRINT TAB(36); USING "###,###########"; two# * mer;
ELSE PRINT TAB(26); "2,305,843,008,139,952,128";
END IF
PRINT " = (2^"; LTRIM\$(STR\$(power)); "-1) * 2^"; LTRIM\$(STR\$(power - 1))
IF power < 31 THEN 1

```
9. Your computer can join the search!

You too could be a part of history. As I mentioned above, two high school students found two of the "Mersenne" prime numbers by running a program on a school computer. Now, home computers are more powerful than school computers were back then.

The GIMPS group has organized a group of volunteers to continue the search. GIMPS stands for the Great Internet Mersenne Prime Search. The last three Mersenne Primes were found by GIMPS volunteers, and you could be the next. There are currently over 4,000 volunteers and anyone who leaves his or her computer on all day and all night long, as I do, can join the GIMPS team.

GIMPS uses thousands of personal computers like yours to search for HUGE prime numbers, a process which can take MILLIONS of computer hours. The more computers join the search, the faster these numbers can be found.

You can join the search by downloading FREE SOFTWARE, reserving a range of numbers that you wish to test, and monitoring the status of the search. To join the search, look for information here.

For more information, see Perfect Numbers, from the St. Andrews MacTutor Math History archives; or search the Dr. Math archives for the words  perfect number  (that exact phrase). The archives provide a List of the First 22 Perfect Numbers.