Perfect Numbers

Ryan Flannery • 12 July 2007

Since some of you were enthused about Lab 6 (testing if a given number is a perfect number), I thought I would put together the following document.

(Re)Introduction to Perfect Numbers

Recall that a perfect number is one that is equal to the sum of its prime factors. A factor of a number is one that divides the number evenly. For example, 2 is a factor of 6 because 6/2=3 and there is no remainder. Equivelently, 3 is a factor of 6 because 6/3=2 with no remainder. Note that for any positive whole number n, 1 is a factor of n.

So, 6 is a perfect number because...

In lab 6, you were all tasked with writing a program to check for perfect numbers from 1 to 10,000. Many of you were suprised by the fact that your programs only found 4 perfect numbers in that range. As you'll find out in the rest of this page, this is expected!

Calculating Perfect Numbers

Every positive whole number is either even or odd. Thus, every perfect number is either even or odd.

Euclid (~300B.C.E.) noticed that the first four perfect numbers were equivalent to 2n - 1(2n - 1) for some n. Not until much later, in the 18th century, did Leonhard Euler prove that every even perfect number is of this form where 2n - 1 is a prime number.

So, every even perfect number can be expressed as 2n - 1(2n - 1) where 2n - 1 is a prime number. Prime numbers that can be expressed as 2n - 1 for some n are called Mersenne prime numbers2. Knowing this, given any Mersenne prime number we can calculate a perfect number.

Currently, there are only 44 known Mersenne prime numbers, and thus only 44 known even perfect numbers. I decided to see how many of the known even perfect numbers I could calculate employing the above equation, while using existing open source software. The calculations were made using the OpenBSD version of the Desk Calculator3 (dc), which a BSD-licensed arbitrary precision arithmetic calculator and programming language, implemented using the OpenSSL BigNum Library4 (bn).

The First 39 Even Perfect Numbers

The below table is the list of perfect numbers I was able to calculate. For each, I display the value of n used in the expression

2n - 1(2n - 1)
as well as the number of digits in the resulting perfect number1, the time it took to calculate the number2, and the size of the number in terms of bytes.

Note that I only generated the first 39 perfect numbers. I would have attempted to calculate the remaining 5 known even perfect numbers, however I was not willing to wait! The 39th (and last) number that I calculated required over 1 hour to generate!

Note also that perfect numbers are not displayed in the table below, but rather stored in seperate text files which each row links to. This is because the numbers tend to get very large, very quick. Note that the last number has over 8 million digits and requires over 8MB of space on disk!

Value of n in
Expression
Number1
of Digits
(approx.)
Time to2
Generate
(approx.)
Size
of File
Perfect
Number3
1 2 1 0s 2B
2 3 2 0s 3B
3 5 3 0s 4B
4 7 4 0s 5B
5 13 8 0s 9B
6 17 10 0s 11B
7 19 12 0s 13B
8 31 19 0s 20B
9 61 37 0s 38B
10 89 54 0s 55B
11 17 65 0s 66B
12 127 78 0s 80B
13 521 318 0s 323B
14 607 371 0s 377B
15 1,279 781 0s 793B
16 2,203 1,346 0s 1.3k
17 2,281 1,393 0s 1.4k
18 3,217 1,965 0s 1.9k
19 4,253 2,598 0s 2.6k
20 4,423 2,702 0s 2.7k
21 9,689 5,919 0s 5.9k
22 9,941 6,073 0s 6.0k
23 11,213 6,850 0s 6.8k
24 19,927 12,179 0s 12k
25 21,701 13,258 0s 13k
26 23,209 14,178 0s 14k
27 44,497 27,183 0s 27k
28 86,243 52,687 0s 52k
29 110,503 67,508 0s 67k
30 132,049 80,671 1s 80k
31 216,091 132,013 2s 131k
32 756,839 462,363 5s 458k
33 859,433 525,039 25s 520k
34 1,257,787 768,399 45s 761k
35 1,398,269 854,222 1m 30s 846k
36 2,976,221 1,818,214 5m 10s 1.8M
37 3,021,377 1,845,800 7m 25s 1.8M
38 6,972,593 4,259,653 37m 47s 4.1M
39 13,466,917 8,227,125 1h 02m 03s 8.0M

What about Odd Perfect Numbers?

Currently, it is unknown whether or not any odd perfect numbers exist. For more information, see the section on "Odd Perfect Numbers" in the Wikipedia entry for perfect numbers (click here)1.

About the Computation

The calculation was performed on my laptop, an Apple PowerBook G4 with 2GB of RAM, running OpenBSD 4.1 (with stable patches).

From output of the script, we can see that the entire script (which generated all of the 39 perfect numbers above) ran for 1 hour 57 minutes and 0.7 seconds. Roughly 65.7% of that time (1 hour 16 minutes and 52.14 seconds) was actual program run time.

The first 29 perfect numbers were generated almost instantly. The next two required 1 and 2 seconds to generate, respectively. After that, we see the time required to generate each number increases rather quickly.

What can you say about the number of calculations (such as multiplications) required in evaluating the expression used? Can you formulate a function which, for a given n, tells you how many multiplications are required, and thus give some indication of the time required to complete the calculation?

Notes

References