bancaldo™

The number 145 is well known for the property that the sum of the factorial
 of its digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of
numbers that link back to 169; it turns out that there are only three such
loops that exist:

169 -> 363601 -> 1454 -> 169
871 -> 45361 -> 871
872 -> 45362 -> 872

It is not difficult to prove that EVERY starting number will eventually
get stuck in a loop. For example,

69 -> 363600 -> 1454 -> 169 -> 363601 (-> 1454)
78 -> 45360 -> 871 -> 45361 (-> 871)
540 -> 145 (-> 145)

Starting with 69 produces a chain of five non-repeating terms,
but the longest non-repeating chain with a starting number below one million
is sixty terms. How many chains, with a starting number below one million,
contain exactly sixty non-repeating terms?

Analisi:

Non molto da dire: ho utilizzato math.factorial per calcolare il fattoriale
di ogni numero. Per calcolare la somma dei fattoriali di ogni cifra di un
numero ho utilizzato un minimo di memoizzazione, per non sforare dal solito
minuto di tempo.
Poi per ogni numero, utilizzo una lista alla quale aggiungo la nuova somma
fino a chè questa somma non è già presente in lista. In caso contrario, con
l’apposita funzione, restituisco la lunghezza di tale lista (catena).
Per il resto è un Brute Force dove conteggio i numeri che hanno una catena di
sessanta elementi.

python:

import time
from math import factorial as fact


START = time.time()

_MEMO = {}
COUNT = 0


def sum_fact(num):
    '''Return the factorization sum'''
    if num not in _MEMO:
        res = 0
        for digit in str(num):
            res += fact(int(digit))
        _MEMO[num] = res
    return _MEMO[num]


def get_chains(num):
    '''Return chain length'''
    chains = []
    while num not in chains:
        chains.append(num)
        num = sum_fact(num)
    return len(chains)

for i in xrange(1, 10 ** 6):
    ch = get_chains(i)
    if ch == 60:
        COUNT += 1

print "Project Euler 74: {}".format(COUNT)
print "elapsed time: {}sec".format(time.time() - START)