math - una - Encontrar suma de factores

usa fichas para mostrar el 2

Question

¿Por qué este código devuelve la suma de factores de un número?

En varios problemas de Project Euler, se le pide que calcule la suma de factores como parte del problema. En uno de los foros, alguien publicó el siguiente código de Java como la mejor manera de encontrar esa suma, ya que en realidad no tiene que encontrar los factores individuales, solo los primarios (no es necesario que conozca Java, puede saltar a mi resumen a continuación):

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;
}

Ahora, lo he intentado muchas veces y veo que funciona. La pregunta es, ¿por qué?

Digamos que factoriza 100 : 1,2,4,5,10,20,25,50,100 . La suma es 217 . La factorización prima es 2*2*5*5 . Esta función te da [5*(5+1)+1]*[2*(2+1)+1] = [25+5+1]*[4+2+1] = 217

Factoring 8 : 1,2,4,8 . La suma es 15 . La factorización prima es 2*2*2 . Esta función te proporciona [2*(2*(2+1)+1)+1]=15

El algoritmo se reduce a (usando Fi para significar el i-ésimo índice del factor F o F sub i):

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

donde m es el número de factores primos únicos, Ni es el número de veces que cada factor único ocurre en la factorización prima.

¿Por qué esta fórmula es igual a la suma de los factores? Supongo que es igual a la suma de cada combinación única de factores primos (es decir, cada factor único) a través de la propiedad distributiva, pero no veo cómo.

Answer 1

El algoritmo esencialmente busca el conjunto de todos los subconjuntos ordenados de los factores primos de n, que es análogo al conjunto de factores de n.

Answer 2

Veamos el caso más simple: cuando n es un poder de un número primo.

Los factores de k^m son 1, k, k ^ 2, k ^ 3 ... k ^ m-1.

Ahora veamos el ciclo interno del algoritmo:

Después de la primera iteración, tenemos k + 1 .

Después de la segunda iteración, tenemos k(k+1) + 1 , o k^2 + k + 1

Después de la tercera iteración, tenemos k^3 + k^2 + k + 1

Y así...

Así es como funciona para los números que son poderes de un solo primo. Podría sentarme y generalizar esto a todos los números, pero es posible que desee darle una oportunidad primero.

EDITAR: Ahora que esta es la respuesta aceptada, elaboraré un poco más mostrando cómo el algoritmo funciona en números con dos factores primos distintos. Entonces es fácil generalizar eso a números con una cantidad arbitraria de factores primarios distintos.

Los factores de x^iy^j son x^0.y^0 , x^0.y^1 ... x^0.y^j , x^1.y^0 ...

Los bucles internos para cada factor primo distinto generan x^i + x^i-1 + ... + x^0 (y de manera similar para y ). Entonces simplemente los multiplicamos juntos y tenemos nuestra suma de factores.