C++ Abundant Number Program

Date: 01/26/2001 at 04:21:05
From: Amaka Agbor
Subject: C++ Abundant Number Program

Is there some computer science C++ formula that allows the user to 
check if a number is abundant, deficient, or perfect? I have to 
write an interactive program that allows the user to enter a positive 
integer, find the sum of the integer, and print if it is abundant, 
deficient or perfect...

Date: 01/26/2001 at 14:02:24
From: Doctor Schwa
Subject: Re: C++ Abundant Number Program

Yes, there is a formula to find the sum of the factors.

There are a few different ways you could do it.

One way, easier to understand but perhaps slower to execute, is
something like this, assuming that "n" is the number that your
user enters:

total = 0
for (low = 1, high = n ; low <= high ; low++, high = n/low)
   if (n % low == 0)
      total = total + low + high;

What that does, for a number like 30 let's say, is start with
low = 1, high = 30, so total now = 31
low = 2, high = 15, so total now = 48
low = 3, high = 10, so total now = 61
low = 4, high = 7, but total doesn't change
low = 5, high = 6, so total now = 72
low = 6, high = 5, so the for loop is done.

There is at least one bug in my program; try it for a number like 9
and the bug I'm thinking of should become apparent. I'll leave it
to you to fix that bug and check whether there are any others.

Another possible method, which will usually be a lot faster for
big numbers, first produces the prime factorization of the number.

Suppose you already have the prime factorization, so prime[i] is the 
ith prime number, and exponent[i] is the exponent that it's raised to,
so for our example of 30, 

the prime array has 2,3,5 in it
and the exponents are 1,1,1
since 30 = 2^1 * 3^1 * 5^1.

I'll say "last" = 3, since there are 3 different primes in the list.

If you have that, then a clever shortcut for finding the sum of the 
factors of a number is as follows:

total = 1
for (i = 0 ; i < last ; i++)
{
   for (j = 0, sum = 0 ; j < exponent[i] ; j++)
   {
       sum = sum * prime[i] + 1;
   }
   total *= sum;
}

Now for our example of 30,
sum = 1, sum = 3, and then total = 3;
sum = 1, sum = 4; and then total = 12;
sum = 1, sum = 6, and then total = 72.

Magic?  Well, if you try distributing (1 + 2) (1 + 3) (1 + 5), you'll 
see all the factors of 30 appear.

Similarly, if you distribute (1 + 2 + 2^2 + 2^3)(1 + 3 + 3^2), you'll 
find all the factors of 2^3 * 3^2 = 72 in that list.

I hope at least one of those algorithms makes sense to you.  If not,
please write us back for some clarification.

Have fun,

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/