Find sum of factors

Question

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

In several Project Euler problems, you are asked to compute the sum of factors as a part of the problem. On one of the forums there, someone posted the following Java code as the best way of finding that sum, since you don't actually have to find the individual factors, just the prime ones (you don't need to know Java, you can skip to my summary 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've tried it many times and I see that it works. The question is, why?

Say you factor 100: 1,2,4,5,10,20,25,50,100. The sum is 217. The prime factorization is 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. The prime factorization is 2*2*2. This function gives you [2*(2*(2+1)+1)+1]=15

The algorithm boils down to (using Fi to mean 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 number of unique prime factors, Ni is the number of times each unique factor occurs in the prime factorization.

Why is this formula equal to the sum of the factors? My guess is that it equals the sum of every unique combination of prime factors (i.e. every unique factor) via the distributive property, but I don't see how.

Weatherspoon

I think you mean [2*(2*(2+1)+1)+1]=15 – Hardigg

@Adrian Petrescu: Yep, thanks. I'll fix it – Weatherspoon

Answer 1

Let's look at the simplest case: when n is a power of a prime number.

The factors of 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...

---

That's how it works for numbers that are powers of a single prime. I might sit down and generalize this to all numbers, but you might want to give it a go yourself first.

EDIT: Now that this is the accepted answer, I'll elaborate a bit more by showing how the algorithm works on numbers with two distinct prime factors. It is then straightforward to generalize that to numbers with an arbitrary amount of distinct prime factors.

The factors of x^i.y^j are x^0.y^0, x^0.y^1 ... x^0.y^j, x^1.y^0...

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

Bluebeard

Got it! If a number A=k^mp^n, the factors will be 1,k,k^2...k^m, 1,p,p^2...p^n and every combination of an item from these two. Each factor as an entry in a matrix, the first row would be 1,k,k^2...k^m and the first column 1,p,p^2,...p^n. Any item ij would be k^ip^j. The complement would be the entry n-i,m-j. The first row would be 1,k,k^2...k^m, the second would be p x the first row, the third would be p^2 x the first row, and the final row would be p^n x the first row. Thus, the sum of each entry (that is, every factor of A) equals [1+k+k^2+...+k^m]*[1+p+p^2+...+p^n]. Thanks again – Weatherspoon

Yup, seems like you understand it :) – Bluebeard

Answer 2

The algorithm is essentially looking at the set of all ordered subsets of the prime factors of n, which is analogous to the set of factors of n.

Cowpoke