StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POFind sum of factors
text
Body
copied!<p>Why does this code return the sum of factors of a number?</p> <p>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):</p> <pre><code>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; } </code></pre> <p>Now, I've tried it many times and I see that it works. The question is, why? </p> <p>Say you factor <code>100</code>: <code>1,2,4,5,10,20,25,50,100</code>. The sum is <code>217</code>. The prime factorization is <code>2*2*5*5</code>. This function gives you <code>[5*(5+1)+1]*[2*(2+1)+1] = [25+5+1]*[4+2+1] = 217</code></p> <p>Factoring <code>8</code>: <code>1,2,4,8</code>. The sum is <code>15</code>. The prime factorization is <code>2*2*2</code>. This function gives you <code>[2*(2*(2+1)+1)+1]=15</code></p> <p>The algorithm boils down to (using <code>Fi</code> to mean the ith index of the factor F or F sub i):</p> <pre><code>return product(sum(Fi^k, k from 0 to Ni), i from 1 to m) </code></pre> <p>where <code>m</code> is number of unique prime factors, <code>Ni</code> is the number of times each unique factor occurs in the prime factorization. </p> <p>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.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload