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
Math Forum Home || Math Library || Quick Reference || Math Forum Search