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 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 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 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
|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?