Buscar suma de factores

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

En varios problemas de Project Euler, se le pide que calcule la suma de los 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 principales (no necesita saber Java, puede saltarse 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 usted factor 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 le da [5*(5+1)+1]*[2*(2+1)+1] = [25+5+1]*[4+2+1] = 217

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

El algoritmo se reduce a (usando Fi en el sentido de que el índice i 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 singulares, Ni es la cantidad 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.

Fuente

2010-12-17 Jake Stevens-Haas

Creo que te refieres a [2 * (2 * (2 + 1) +1) +1] = 15 –

@Adrian Petrescu: Sí, gracias. Lo arreglaré –

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

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

Ahora vamos a ver el bucle 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í sucesivamente ...

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.

EDIT: 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^i.y^j son x^0.y^0, x^0.y^1 ... x^0.y^j, x^1.y^0 ...

Los bucles interiores 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.

Fuente

2010-12-17 02:35:41

Gracias, lo intentaré. Un segundo. –

¡Entendido! Si es un número A = k^m * p^n, los factores serán 1, k, k^2 ... k^m, 1, p, p^2 ... p^n y cada combinación de un elemento de estos dos. Cada factor como una entrada en una matriz, la primera fila sería 1, k, k^2 ... k^m y la primera columna 1, p, p^2, ... p^n. Cualquier ítem ij sería k^i * p^j. El complemento sería la entrada n-i, m-j. La primera fila sería 1, k, k^2 ... k^m, la segunda sería px la primera fila, la tercera sería p^2 x la primera fila, y la última fila sería p^nx la primera fila. Por lo tanto, la suma de cada entrada (es decir, cada factor de A) es igual a [1 + k + k^2 + ... + k^m] * [1 + p + p^2 + ... + p^norte]. Gracias de nuevo –

Sí, parece que lo entiendes :) –

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

Fuente

2010-12-17 02:43:21 perimosocordiae

Respuesta

Cuestiones relacionadas