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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.