Perfect Number Algorithms

Date: 03/31/98 at 10:13:45
From: Jonas Nilsson
Subject: Perfect Numbers

Dear Dr. Math,

My problem is to make a C program in which the user inputs an integer, 
and my program should answering back to the user whether the integer 
that has been inputed is a perfect number or not. 

Can you please let me know the formula I need? I would appreciate
it greatly.

Yours sincerely,
Jonas

Date: 03/31/98 at 12:39:43
From: Doctor Rob
Subject: Re: Perfect Numbers

For information on this subject, see the following from the Dr. Math 
FAQ:

  http://mathforum.org/dr.math/faq/faq.perfect.html   

A perfect number is one which is equal to the sum of all its divisors
(besides itself).

One way to find out if a number X is perfect is to find its 
factorization into prime powers, make a list of all the divisors using 
that, add them up, and compare to X. If you get equality, X is 
perfect. If the sum exceeds X, it is called "abundant," and if the sum 
is smaller than X, it is called "deficient."

This method could be very lengthy if X is extremely large! You will 
need a factoring subroutine and a prime-testing subroutine, as well as 
the usual arithmetic. Is there a limit on the size of X?  Perhaps X is 
restricted to single-precision or double-precision integers?

Another way is to use the fact that there is no odd perfect number 
with less than 200 decimal digits, and all the even perfect numbers 
have the special form 2^(n-1)*(2^n-1), where 2^n-1 is a prime number 
(called a Mersenne prime). If X has less than 200 decimal digits, n 
can have any of the following values: 2, 3, 5, 7, 13, 17, 19, 31, 61, 
89, 107, 127, 521, or 607, and no others. Take the number X and 
divide out as large a power of 2 as you can, 2^k = p, so X/p is odd.  
If k+1 is not on the list, then X is not perfect. If k+1 is on that 
list, and X/p = 2*p - 1, then X is perfect, but if X/p has any other 
value, X is not perfect. If X has more than 200 digits and is even, 
the list can be extended, but if it is odd, you probably cannot deal 
with the problem this way.

-Doctor Rob,  The Math Forum
Check out our web site! http://mathforum.org/dr.math/