Finding the Sum of the Factors of a Number

Date: 07/25/2007 at 15:04:55
From: adm
Subject: Sum of Factors

Is there a formula to find the SUM of all the factors?

Date: 07/25/2007 at 23:00:04
From: Doctor Greenie
Subject: Re: Sum of Factors

Hi, adm --

I assume you mean a formula for finding the sum of the factors of a 
given number.

Yes, there is a formula, or perhaps it should be called an algorithm.
It is difficult to put it into the form of a formula, but the process
is easy to understand.

Let's look at a relatively simple example to understand how the 
"formula" works.  Consider the number 18.  Its factors are

  1 2 3 6 9 18

The sum of these factors is 39.  We will find a way to find this sum 
using the prime factorization of the number (without finding all the 
factors and adding them together).

The prime factorization of 18 is

  (2^1)(3^2)

Let's write the factors of 18 again, expressing each one as a 
product of powers of the prime factors 2 and 3:

   1 = (2^0)(3^0)
   2 = (2^1)(3^0)
   3 = (2^0)(3^1)
   6 = (2^1)(3^1)
   9 = (2^0)(3^2)
  18 = (2^1)(3^2)

Now let's use these forms of the factors to write the sum of all the 
factors; then we will rearrange the terms in that sum to develop a 
formula for finding the sum WITHOUT finding all the factors and 
adding them together.

  sum of factors = (2^0)(3^0) + (2^1)(3^0) + (2^0)(3^1) +
                   (2^1)(3^1) + (2^0)(3^2) + (2^1)(3^2)

  sum of factors = (2^0)(3^0) + (2^0)(3^1) + (2^0)(3^2) +
                   (2^1)(3^0) + (2^1)(3^1) + (2^1)(3^2)

  sum of factors = (2^0)(3^0 + 3^1 + 3^2) + (2^1)(3^0 + 3^1 + 3^2)

  sum of factors = (2^0 + 2^1)(3^0 + 3^1 + 3^2)

  sum of factors = (1 + 2)(1 + 3 + 9)
 
  sum of factors = (3)(13) = 39

Look at the equation as it stands on the next-to-last line above.  The 
first factor in the expression on the right is the sum of the powers 
of 2 up to the first power; the second factor is the sum of the powers 
of 3 up to the second power (as is easily seen in the preceding line).  
When we multiply these two expressions together, we get terms which 
consist of exactly every possible combination of powers of 2 from 0 to 
1 and powers of 3 from 0 to 2.  But those combinations are exactly the 
factors of the original number.

So the process for finding the sum of all the factors of the number 
consists of the following steps:

  (1) find the prime factorization
  (2) form a product in which each term is the sum of all the powers
      of one of the prime factors up to the exponent on that prime 
      factor in the prime factorization

That product is the sum of the factors of the number.

Here are a couple of more examples....

(A)  28...

(You may know that this is a perfect number; the sum of its PROPER 
factors is the number itself--so the sum of ALL the factors should 
be twice the number.)

  28 = (2^2)(7^1)

  sum of factors = (1 + 2 + 4)(1 + 7) = (7)(8) = 56

(B)  200...

  200 = (2^3)(5^2)

  sum of factors = (1 + 2 + 4 + 8)(1 + 5 + 25) = (15)(31) = 465

(C)  9000...

  9000 = (2^3)(3^2)(5^3)

  sum of factors = (1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 5 + 25 + 125) =
                   (15)(13)(156) = 30420

I hope this helps.  Please write back if you have any further 
questions about any of this.

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

Date: 07/25/2007 at 23:46:38
From: adm
Subject: Thank you (Sum of Factors)

Thank you very much, Doctor Greenie.  More power to you.

Adm