Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
High School Number Theory

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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/