Finding a Number Given the Sum of Its FactorsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/