Proyecto de Euler, el Problema nº 565 estados:
Deje $\sigma(n)$ ser la suma de los divisores de a $n$. E. g. los divisores de $4$$1, 2$$4$, lo $\sigma(4)=7$.
Los números de $n$ que no exceda $20$ tal que $7$ divide $\sigma(n)$ son: $4, 12, 13$$20$, la suma de estos números se $49$.
Deje $S(n, d)$ la suma de los números de $i$ que no exceda $n$ tal que $d$ divide $\sigma(i)$.
Por lo $S(20, 7)=49$.
Se le da: $S(10^6, 2017)=150850429$ $S(10^9, 2017)=249652238344557$
Encontrar $S(10^{11}, 2017)$
He escrito un programa en Java que se encuentra la solución a $S(20, 7)$ sobre $0.001$ segundos en mi equipo. El mismo programa tarda un poco más de $7$ segundos para encontrar la solución a $S(10^6, 2017)$. Sin embargo, aparentemente tarda una eternidad para ejecutar $S(10^9, 2017)$. No me he molestado tratando de encontrar la $S(10^{11}, 2017)$ hasta que se me puede venir para arriba con una manera mucho más eficiente.
Dado que estos son problemas matemáticos destinados a ser resuelto por un equipo, tengo que encontrar y explotar algo de matemáticas para mejorar notablemente el tiempo de ejecución de mi programa.
Una de las primeras cosas que me llamó la atención cuando vi a este problema es que he utilizado el divisor de la función y su multiplicativo de la propiedad antes de venir para arriba con un estilo elegante y muy eficiente método para resolver un Proyecto anterior de Euler programa. Así que, hice una referencia a la función de divisor artículo de wiki, una vez más, para encontrar algo que me ayudara, pero no entiendo lo suficiente de las matemáticas para beneficiarse de ella.
También he utilizado un conocido algoritmo que se enseña en la mayoría de Introducción a los cursos de informática con el fin de buscar de forma eficiente los divisores de cada uno de los $n$ y se suman a ellos.
El pseudocódigo del algoritmo que se utiliza es la siguiente:
1. Input an integer n
2. Set a variable named sum equal to 0
3. Set a variable named limit to be the sqrt(n)
3. Run a loop from i = 1 to i <= limit
if n is divisible by i, then add i to sum
if i does not equal (n / i), then add (n / i) to sum
4. Return the sum
En la medida de mis conocimientos, este algoritmo es el más rápido que hay para encontrar los divisores de los números enteros. He utilizado este algoritmo para implementar la suma de los divisores de la función en mi programa.
La siguiente parte es lo que sospecho que está haciendo el mi código de manera ineficiente. Sigue el $S(n, d)$ función de que el Proyecto de Euler se describe. Aquí está el pseudocódigo para la implementación de mi $S(n, d)$:
1. Input an integer n
2. Input an integer d
3. Set a variable named sumNums equal to 0
4. Run a loop from i = 1 to i <= n
if d divides sumOfDivisors(i), then add i to sumNums
5. Return sumNums
Por lo tanto, mi pregunta es, ¿qué hecho matemático(s) y/o teoremas puedo utilizar para hacer mi programa de encontrar la solución rápidamente?
