Finding a Number Given the Sum of Its Factors

Date: 10/19/2007 at 02:42:57
From: Jean-Louis
Subject: Prime Factor

Let's take, for example, the number 91.  The factors of 91 are: 1  7 
13  91.  The prime factors are:  7 x 13.  The sum of the factors is:
1+7+13+91= 112.

Now, my question is: If the sum of the factors of a number is given,
how would you then find this number?

Say the sum of the factors is 91.  Is there a formula to determine
this number?  I had to do it the brutal way.  I've tried several 
numbers in order to reach the sum 91.

I found that 36 is the number, because
The factors of 36 are: 1  2  3  4  6  9  12  18  36  
The prime factors are:  2 x 2 x 3 x 3
The sum of the factors is: 1+2+3+4+6+9+12+18+36 = 91

Is there a better way to find a number if the sum of its divisors is 
known?

Thanks.  

Date: 10/19/2007 at 18:23:25
From: Doctor Greenie
Subject: Re: Prime Factor

Hi, Jean-Louis -

There is a quick way to find the sum of the factors of a number 
without finding all the factors and adding them together.  Let me 
demonstrate with your example where the number is 91.

As you show, the prime factorization of 91 is 7*13.  The sum of its 
factors, found by adding the factors, is

  1 + 7 + 13 + 91 = 112

This sum can be found without knowing all the individual factors as 
follows:

  (1+7)(1+13) = 8*14 = 112

If we multiply the expressions in the two sets of parentheses as if 
they were binomials, we get an expression which is the list of all 
the factors:

  (1+7)(1+13) = 1 + 7 + 13 + 91

Notice that the expression in the first set of parentheses is the sum 
of the powers of 7 from 0 to 1; likewise the expression in the second 
set of parentheses is the sum of the powers of 13 from 0 to 1.

  (7^0 + 7^1)(13^0 + 13^1) =
  (7^0)(13^0) + (7^1)(13^0) + (7^0)(13^1) + (7^1)(13^1) =
  1 + 7 + 13 + 91

Perhaps you can see how this process will produce every possible 
combination of the prime factors of the number, thus producing every 
factor of the number.

So we have a process for finding the sum of the factors of a number 
without finding all the factors.  For the number 1800, the prime 
factorization is

  1800 = (2^3)(3^2)(5^2)

The sum of all the factors of 1800 is then

  (1+2+4+8)(1+3+9)(1+5+25) = 15*13*31 = 6045

So now to your question.  Given, for example, the sum of the factors 
of the number as being 112, how do we determine that the number is 
91?  The answer is, we look at how we can get the number 112 by 
multiplying expressions of the form in the parentheses.  The numbers 
we can multiply are only sums of powers of prime numbers:

  sums of powers of 2: 1, 3, 7, 15, 31, 63, 127, ...
                 of 3: 1, 4, 13, 40, 121, ...
                 of 5: 1, 6, 31, 156, ...
                 of 7: 1, 8, 57, ...
                 of 11: 1, 12, 133, ...
                 of 13: 1, 14, 183, ...
                 of 17: 1, 18, ...
                 of 19: 1, 20, ...
  ... and so on.

So a partial list of the numbers we could POSSIBLY multiply together 
to get a sum of the factors of a number is

  1, 3, 4, 6, 7, 8, 12, 13, 14, 15, 18, 20, ...

The only numbers in this list that we can multiply together to get a 
product of 112 are 8 and 14:

  112 = 8*14 = (1+7)(1+13)

And so the number for which the sum of the factors is 112 is

  (7^1)(13^1) = 7*13 = 91

For your other example, given that the sum of the factors of the 
number is 91, the ONLY way we can get a product of 91 (other than 
91*1) is 7*13.  Both those numbers are in our list:

  91 = 7*13 = (1+2+4)(1+3+9)

and so the number for which the sum of the factors is 91 is

  (2^2)(3^2) = 4*9 = 36

Now for an example which is not part of your message: find a number 
for which the sum of the factors is 224.

We look at our list of possible numbers to multiply together to get 
this product of 224:

  1, 3, 4, 6, 7, 8, 12, 13, 14, 15, 18, 20, ...

224 is not divisible by 3.  It is divisible by 4; 224/4 = 56; and 56 
is 7*8, and both these numbers are in our list.  So ONE number for 
which the sum of the factors is 224 can be found as follows:

  224 = 4*7*8 = (1+3)(1+2+4)(1+7)

And so ONE number for which the sum of the factors is 224 is

  (3^1)(2^2)(7^1) = 84

So, it's not exactly a magic formula which will immediately find 
a number for which the sum of the factors is a given number, but it 
is a well-defined method which makes blind guessing unnecessary.

I hope all 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/