|
|
Perfect Numbers 
What is a perfect number? How do you find them? How many are there?A contribution from John Knoderer, the MazeMan:
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.
The factors of 6 are 1, 2, 3 and 6.
The factors of 28 are 1, 2, 4, 7, 14 and 28.
The factors of 496 are 1, 2, 4, 8, 16, 31, 62, 124, 248 and 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.
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.
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, 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
So, our first five perfect numbers are
4 * 7 = 28 16 * 31 = 496 64 * 127 = 8,128 4096 * 8191 = 33,550,336
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
(2^18) * (2^19 - 1) = 137,438,691,328 (2^30) * (2^31 - 1) = 2,305,843,008,139,952,128
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).
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.
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.
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
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, 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
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.
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^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
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.)
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 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)
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)
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
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 5Don'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
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.
AAC Mr Maze www.MAZES.com
For more information, see Perfect Numbers, from the St. Andrews MacTutor Math History archives; or search the Dr. Math archives for the words
|
[Privacy Policy] [Terms of Use]
Math Forum Home ||
Math Library ||
Quick Reference ||
Math Forum Search