¿Cómo puedo determinar el límite superior más ajustado para el problema 30 en el Proyecto Euler?

Answer 1

Puede haber otras formas además de reducir el límite superior. Puedo pensar en al menos 2 formas:

1) Tamaño de paso mayor que uno : considere el número 23. La suma de las quintas potencias de sus dígitos es 275. Ahora tenga en cuenta que si aumenta 23 en uno, aumenta la suma en al menos uno, ya que (x + 1) ^ 5 – x ^ 5> = 1, donde x es el dígito de las unidades. Por lo tanto, no necesita verificar los números del 24 al 29. Las cosas se vuelven difíciles a los 30. Por lo tanto, al usar un poco de lógica, debería poder saltar de un múltiplo de 10 al siguiente sin verificar todos los números intermedios.

2) Use la combinación en lugar de la permutación : tenga en cuenta que mientras revisa números de 5 dígitos, considera todos los números 12345, 12354, 12435, … cuando la suma de las quintas potencias para todos estos números es la misma. Si considera el conjunto de números {1, 2, 3, 4, 5}, puede encontrar la suma de las quintas potencias y simplemente verificar si la suma tiene exactamente estos dígitos. De esa manera, ¡puedes eliminar a los 5! números a la vez. Haga esto para todos los conjuntos posibles de todos los tamaños hasta 6.

Answer 2

La mayor suma posible de dígitos para n dígitos es
[matemáticas] n * 9 ^ 5 [/ matemáticas]

Verificando esto para valores pequeños de n da números de 6 dígitos cuando n = 7.

Entonces [math] n = 7 [/ math] debería ser un límite lo suficientemente bueno.