Associated Topics || Dr. Math Home || Search Dr. Math

### 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
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.

if you have questions about what I've written above.

- Doctor Paul, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Calculators, Computers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search