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.
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!
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 2^{n  1}(2^{n}  1) for some n. Not until much later, in the 18^{th} century, did Leonhard Euler prove that every even perfect number is of this form where 2^{n}  1 is a prime number.
So, every even perfect number can be expressed as 2^{n  1}(2^{n}  1) where 2^{n}  1 is a prime number. Prime numbers that can be expressed as 2^{n}  1 for some n are called Mersenne prime numbers^{2}. 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 Calculator^{3} (dc), which a BSDlicensed arbitrary precision arithmetic calculator and programming language, implemented using the OpenSSL BigNum Library^{4} (bn).
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
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 39^{th} (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 
Number^{1} of Digits (approx.) 
Time to^{2} Generate (approx.) 
Size of File 
Perfect Number^{3} 


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