In searching for answers about counting divisors over the last couple weeks, I found a few that are about the similar question of finding the sum of a number’s divisors. In fact, a couple questions and answers confuse the two problems. Let’s finish off the topic by looking at these. (Keep in mind that “divisor” and “factor” are used almost interchangeably.)
Almost a formula
We’ll start with this straightforward question from 2007:
Finding the Sum of the Factors of a Number Is there a formula to find the SUM of all the factors?
Doctor Greenie answered:
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.
What he will show is a simple process, illustrated by an example, but we’ll be making it into something more like a formula before we’re done.
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).
This establishes the goal; it’s important to have a clear idea what we are trying to do. Here, the number of divisors (factors) of \(18 = 2^1\times 3^2\) is \((1+1)(2+1) = (2)(3) = 6\), as we saw a couple weeks ago: the sum of one more than each exponent in the prime factorization. The sum of the divisors is \(1+2+3+6+9+18 = 39\). How can we find that from the prime factors?
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)
As we’ve seen before, we make this list by combining each possible power of 2 (exponents 0 and 1) and each possible power of 3 (exponents 0, 1, and 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
He has first ordered the factors, grouping those with \(2^0\) followed by those with \(2^1\), and similarly putting powers of 3 in order within each group. Then he factored out the power of 2 from each group, and then factored out the common factor \((3^0+3^1+3^2)\). You may know this as “factoring by grouping”.
Our formula, such as it is, is \((2^0 + 2^1)(3^0+3^1+3^2)\).
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.
When we expand (distribute) our formula, we multiply each power of 2 times each power of 3, which is exactly what we did in making our list of factors!
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 factor 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.
This would be more complicated written as a formula than written in words. We’ll see how to write it more compactly below. In the absence of an actual formula, more examples can help make sure you see the idea:
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
In the last example there are three different primes, but the same idea extended naturally.
The student replied,
Thank you very much, Doctor Greenie. More power to you.
I’m not sure if that was a pun.
Prove the formula
Now here’s a question from 2013, offering a formula and asking for a proof:
Sum of Divisors Proven What is the proof of the formula for the total number of divisors of any integer? I know about this formula and its proof: A = P^a * Q^b * ... * Z^n => (a + 1)(b + 1) ... (n + 1) I want to prove [P^(a + 1) - 1]/(P - 1) * [Q^(a + 1) - 1]/(Q - 1) * ... ... * [Z^(n + 1) - 1]/(Z - 1) I've thought about this, but haven't gotten anywhere, so I request you to help me. Please ... I cannot prove it.
You may notice that the first formula is for the number of divisors of a number \(A = P^aQ^b\cdots Z^n\) where P, Q, …, Z are its prime factors and a, b, …, n are the exponents, namely: $$\text{Number of divisors of }A = (a+1)(b+1)\cdots (n+1)$$
What he wants to prove is a formula for the sum of the divisors of A, namely $$\text{Sum of divisors of }A = \frac{P^{a+1}-1}{P-1}\cdot \frac{Q^{b+1}-1}{Q-1}\cdot \cdots \cdot \frac{Z^{n+1}-1}{Z-1}$$
I answered, first correcting what he had said:
Hi, Arghavan. Possibly the reason for your difficulty is that your second formula is NOT for the NUMBER of divisors; it is the formula for the SUM of the divisors of any number.
It isn’t quite clear whether Arghavan just wrote “total number” when he meant just “total”, or actually thought the second formula was for the number of divisors. But it was clear that the formula he wanted to prove was for the sum. What was least clear was whether he wanted a formal, detailed proof, or just a convincing argument. In the former case, I offered two sources:
You can find a proof (written in a sophisticated form) at PlanetMath: Formula for sum of divisors https://planetmath.org/formulaforsumofdivisors The same thing can be found, in a form more suitable for your first exposure to it (but not in the form of a complete proof), at MathWorld, in equations 8-16 of Divisor Function http://mathworld.wolfram.com/DivisorFunction.html
Both of these use more advanced notation and concepts than were used in the question, so I presumed something more basic would be needed. I took a somewhat different approach than Doctor Greenie, but similarly started with an example:
I'll just illustrate the idea behind the proof by showing how it works with a simple number, so you can more easily follow what they do.
Consider first a number that is a power of a prime:
A = 2^3 = 8
The divisors of A are 1, 2, 4, 8; that is, 2^0, 2^1, 2^2, and 2^3. The sum of these forms a geometric series, so we can use the appropriate formula to find the sum:
2^4 - 1
S(A) = 2^0 + 2^1 + 2^2 + 2^3 = --------- = 15
2 - 1
Similarly for
B = 3^2 = 9
The sum of its divisors is
3^3 - 1
S(B) = 3^0 + 3^1 + 3^2 = --------- = 13
3 - 1
The use of the formula for a geometric series is where this formula goes beyond Doctor Greenie’s. Here is a quick derivation of that formula, in case you haven’t seen it:
Suppose $$S = a + ar + ar^2 + \cdots + ar^n$$
Then, multiplying by S, $$rS = ar + ar^2 + \cdots + ar^n + ar^{n+1}$$
Subtracting, $$rS – S = ar^{n+1} – a = a\left(r^{n+1} – 1\right)$$
Therefore, solving for S, $$S = \frac{a\left(r^{n+1} – 1\right)}{r – 1}$$
In our application, \(a = 1\).
Continuing:
Now, consider a number formed by multiplying powers of two primes: any divisor of ... C = 2^3 * 3^2 = 72 ... is the product of a power of 2 and a power of 3. We can obtain the sum by multiplying the two sums found above: S(C) = (2^0 + 2^1 + 2^2 + 2^3)(3^0 + 3^1 + 3^2)
Where Doctor Greenie built up to this, showing how you might think of it, I have leaped to the factored form, which you can check, as I do next:
In order to see this, expand the product (distribute) and you get
(2^0)(3^0) + (2^1)(3^0) + (2^2)(3^0) + (2^3)(3^0)
+ (2^0)(3^1) + (2^1)(3^1) + (2^2)(3^1) + (2^3)(3^1)
+ (2^0)(3^2) + (2^1)(3^2) + (2^2)(3^2) + (2^3)(3^2)
This means
1 + 2 + 4 + 8
+ 3 + 6 + 12 + 24
+ 9 + 18 + 36 + 72 = 195
This is the sum of the twelve divisors of C.
Applying the geometric series formula to my formula for S(C), we have:
So the sum of divisors is the product of the sums we already worked out:
2^4 - 1 3^3 - 1
S(C) = --------- * --------- = 15 * 13 = 195
2 - 1 3 - 1
This is what the formula you asked about does.
I closed with links to two explanations of the other formula (neither of which I included in my post two weeks ago), and Doctor Greenie’s answer above:
By the way, we have a couple explanations of the formula for the number of divisors. Even though you already have a proof, there may be something here that is of interest to you: The Number of Divisors of an Integer http://mathforum.org/library/drmath/view/55843.html How Many Factor Pairs Does a Given Number Have? http://mathforum.org/library/drmath/view/65130.html We also have this answer that doesn't quite give the formula for the sum, but gives most of the reasoning: Finding the Sum of the Factors of a Number http://mathforum.org/library/drmath/view/71550.html
Reversing the process
Here’s a twist on the question, from 2007, similar to some we saw on the number of factors:
Finding a Number Given the Sum of Its Factors 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?
Doctor Greenie took this one, starting with a quick version of his approach to finding the sum:
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.
A harder example is more typical:
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
Now we want to reverse this, so that given the sum 6045, we could find the number 1800. Doctor Greenie won’t be solving that one … but we will!
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.
Each of these lists is a sequence that starts with 1 and successively adds \(p, p^2, p^3, \dots\). For sums of powers of 2, he successively added 2, 4, 8, 16, … . How do we know when to stop? We’ll see.
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
So in each row, we can stop when the next number would be past 112, which is what he did; the only way other possibilities could have appeared would be to use more rows, and if you try that you will see that nothing has been missed.
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
So we’ve solved each example that was offered. How about another?
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
This example used three prime factors, which was important to show. But note that the three factors had to come from different rows (different primes), so it may be best not to use the single combined list for the final choice.
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.
Let’s be bold and try finding a number whose divisors sum to 6045! That factors as \(3\cdot 5\cdot 13\cdot 31\). Can we get that from our numbers, each from a different prime? Yes; 15 comes from \(2^3\); 13 comes from \(3^2\); 31 comes from \(5^2\). So our number can be \(2^3\cdot 3^2\cdot 13\cdot 5^2 = 1800\). We did it!
An interesting extra challenge would be to find a number that is the sum of the divisors of two different numbers. I see nothing (yet) to prevent that.