Find the sum of factors

Question

Why does this code return the sum of the factors of a number?

In several Project Euler problems, you will be asked to calculate the sum of the factors as part of the problem. On one of the forums there, someone posted the following Java code as the best way to find this amount, since you actually do not need to find individual factors, just the main ones (you do not need to know Java, you can go to my resume below):

public int sumOfDivisors(int n) { int prod=1; for(int k=2;k*k<=n;k++){ int p=1; while(n%k==0){ p=p*k+1; n/=k; } prod*=p; } if(n>1) prod*=1+n; return prod; } 

Now I have tried this many times, and I see that it works. The question is why?

Say you have a ratio of 100 : 1,2,4,5,10,20,25,50,100 . The sum is 217 . Primary factorization 2*2*5*5 . This function gives you [5*(5+1)+1]*[2*(2+1)+1] = [25+5+1]*[4+2+1] = 217

Factoring 8 : 1,2,4,8 . The sum is 15 . Primary factorization 2*2*2 . This function gives you [2*(2*(2+1)+1)+1]=15

The algorithm reduces to (using Fi to denote the ith index of the factor F or F sub i):

 return product(sum(Fi^k, k from 0 to Ni), i from 1 to m) 

where m is the number of unique simple factors, Ni is the number of times that each single factor occurs in simple factorization.

Why is this formula equal to the sum of the factors? I assume that it is equal to the sum of each unique combination of simple factors (i.e., Each single factor) through the distribution property, but I do not see how.

Answer 1

Consider the simplest case: when n is a prime power.

The factors k^m are 1, k, k ^ 2, k ^ 3 ... k ^ m-1.

Now let's look at the inner loop of the algorithm:

After the first iteration, we have k + 1 .

After the second iteration, we have k(k+1) + 1 or k^2 + k + 1

After the third iteration, we have k^3 + k^2 + k + 1

And so on...

---

How this works for numbers that are powers of one prime. I could sit down and generalize this to all numbers, but first you may want to go first.

EDIT: Now that this is the accepted answer, I’ll talk a little bit more about how the algorithm works on numbers with two different main factors. Then it is easy to generalize this to numbers with an arbitrary number of different simple factors.

The factors x^iy^j are x^0.y^0 , x^0.y^1 ... x^0.y^j , x^1.y^0 ...

The inner loops for each individual prime factor generate x^i + x^i-1 + ... + x^0 (and similarly for y ). Then we just multiply them together, and we have our own sum of factors.

Answer 2

The algorithm essentially considers the set of all ordered subsets of prime factors n, which is similar to the set of factors n.