Perfect Number Algorithm

Date: 10/24/2001 at 00:34:29
From: Cristopher Wick
Subject: An algorithm for testing a number to see if it is perfect.

I'm having a smidge of trouble creating an algorithm to test whether 
or not a number is a Perfect Number. I'm trying to find one that 
would be easily translatable into C++ code. Do you have an algorithim 
that might help?

Date: 10/24/2001 at 12:06:08
From: Doctor Paul
Subject: Re: An algorithm for testing a number to see if it is 
perfect.

There are really two approaches you can take here. The first is easy, 
but it is probably not what your teacher had in mind if this is for a 
class assignment.

There are only 38 perfect numbers known. Program them into an array 
and then input the number to be checked. Just run a for loop from 1 to 
the length of the array that checks each entry in the array against 
the number to be checked.

The computer should take about 2 seconds to decide whether or not your 
number is perfect.  :-)

If you want to do it this way, you should be asking, "What are the 
known perfect numbers?"

First a digression:

A Mersenne prime is a number of the form 2^p - 1 that is prime.

For example, 2^3 - 1 = 7.  So 7 is a Mersenne prime.

2^p - 1 will never be prime if p is not prime. So you only need to 
check prime exponents. But not all prime exponents produce Mersenne 
primes. For example, 2^11 - 1 = 2047 = 23 * 89.
 
Mersenne primes and perfect numbers are intimitely related:

If k = 2^p - 1 is a Mersenne prime, then:

k * 2^(p-1) is perfect.

So the search for perfect numbers has been relegated to the search for 
Mersenne primes.  Thus far, 38 Mersenne primes have been found. The 
Great Internet Mersenne Prime Search (GIMPS) Project is ongoing:  

   http://mersenne.org/   .

GIMPS has found the last 4 Mersenne Primes. You can get a list of them 
here:

   http://www.utm.edu/research/primes/mersenne.shtml   

The current world record prime is the 38th Mersenne prime:

   2^6972593 - 1 has 2,098,960 digits.

The perfect number will be even larger.  

So maybe your array won't be able to hold such a large number.

This is probably the case. But the other method (described below) 
requires you to factor this large number. Your routine probably won't 
be able to do that either!


The other method would be as follows:

Write an algorithm that produces the factors of the integer to be 
tested and then add them up and compare to the integer to be tested.

For example:

To verify that 28 is perfect, your program woudld produce the factors 
of 28: [1,2,4,7,14,28], and then sum all except the last one to obtain 
28, which proves that 28 is perfect.


Factoring algorithms are hard to come by and our inability to factor 
large integers has led to much of the security of Internet 
transactions (see RSA Security, http://rsasecurity.com/   ). If you use 
Netscape, type "about:" in the address window (where you normally type 
http://www... ) and you'll see that RSA Security provides encryption 
mechanisms used in Netscape. The RSA encryption algorithm would not be 
secure if we could quickly factor large integers.

But for "small" numbers, you should be able to write a primitive 
factoring algorithm as follows:

First notice that the factors of a number come in pairs; for example: 
the factors of 48 are:  

   [1,2,3,4,6,8,12,16,24,48]

But we can view them this way: 

   [ {1,48}, {2,24}, {3,16}, {4,12}, {6,8} ] 

So if I know that 6 is a factor, I can find out that 8 goes with it by 
dividing 6 into 48.

The smaller factor in each pair of factors must occur before 
floor(sqrt(48))

So run a for loop for i from 2 to floor(sqrt(n)) and check to see if 
each i divides n evenly.

You can use the mod operator (% I think) to test divisibility.  For 
example:

3 divides 48 so 48 % 3 will give 0.

Whenever n % i is zero, you have found a factor. Once you have found a 
factor, place it in an array. Then right next to it, place its pair - 
n/i

So if you did this for n = 48, your array would be:

   [1,48,2,24,3,16,4,12,6,8]

Now sort this array in increasing order to obtain:

   [1,2,3,4,6,8,12,16,24,48]

Call this array A.

and now add all but the last entry:

for p from 1 to length(A)-1

value = value + A[p]

When done, if value = n then n is perfect.

This algorithm works well for relatively small numbers. Notice 
that to find all of the factors of 1,000,000 (and hence test 
whether or not 1,000,000 is perfect) it only has to test up to 
floor(sqrt(1,000,000)) = 1000.

I wrote a similar routine for my TI-86 Graphing Calculator. It can 
tell me the sum of the factors of 100,000, not counting 100,000 of 
course, in less than 20 seconds (the answer is 146,078). Certainly a 
c++ routine should be able to do it almost instantaneously.

Feel free to write back if you'd like to talk about this some more or 
if you have questions about what I've written above.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/