Factoriones

Hace tiempo que no entro a resolver problemas en Project Euler. Si te gusta resolver acertijos matemáticos, que seguido involucren habilidades de programación, es bastante recomendable. El punto es que recordé un problema que implícitamente pide encontrar factoriones.Los pide implícitamente pues sólo existen cuatro factoriones en base 10. Un factorion es un número que es igual a la suma de factoriales de sus dígitos, e.g. 145=1!+4!+5!

Para hallarlos simplemente hay que programar directamente el algoritmo para discriminar si un número es o no factorion. El verdadero problema es que el programa no pase días buscando factoriones. Para lograr esto, el procedimiento estándar es notar que k(9!) tendrá menos de k dígitos siempre que k>7, por tanto sólo hay que buscar factoriones hasta 7(9!)=2540160

Ahora bien, esto aún sigue sin ser muy eficiente. Esto es simplemente un puzzle de programación, como dije sólo existen cuatro factoriones, se conocen y punto.

El factorion más grande es 40585, así que probablemente exista una forma de recortar el límite superior a partir de un argumento lógico. Mi lenguaje ya predilecto es Python, y no sé si sea precisamente si es él el que hace lento el programa.

Acá comparto el código:

# 145 es un numero curioso, ya que 1! + 4! + 5! = 1 + 24 + 120 = 145.
# Encuentra la suma de todos los numeros iguales a la suma
# del factorial de sus digitos.
# Nota: como 1! = 1 y 2! = 2 no son sumas, no se incluyen.

import time
t0 = time.time()

def factorial(n):
    if n > 1: return (n*factorial(n-1))
    else: return 1

for i in range(1, 7*factorial(9)): # LIMITE SUPERIOR ÓPTIMO~1*(10^5)
    n, s = str(i), 0
    for j in range(len(n)):
        s += factorial(int(n[j]))
    if s == i: print(i)
print('Tiempo de ejecucion: ',time.time()-t0,'segundos.')