[EP 074] f(145) = 1! + 4! + 5! = 145

정수에 대해서 그 정수를 십진수로 표현했을 때, 각 자리수의 계승(팩토리얼)의 합을 취하는 조작이 있다. 어떤 정수에서 시작하더라도 이 조작을 반복하면 어떤 루프를 돌게 된다. 이 루프는 링크에서 말한 것 밖에 없다고 한다. 이걸 알고서... 1000000보다 작은 정수 중에서 그 정수에서부터 시작하여, 조작을 반복하여 만들어지는 수의 집합의 갯수가 60개인 것들의 갯수를 구하란다.

#!/usr/bin/env python


# http://projecteuler.net/index.php?section=problems&id=74
# factorial list
from functools import lru_cache


factorial = [1]  # 0! = 1
for i in range(1, 10):
    factorial.append(factorial[i - 1] * i)  # n! = n*(n-1)!
print(factorial)
# input()


# @lru_cache()
def factorial_sum_tup(t: tuple):
    if len(t) == 1:
        return factorial[t[0]]

    return factorial[t[0]] + factorial_sum_tup(t[1:])


def factorial_sum(n: int):
    """
    When n = abcdef,  returns a! + b! + c! + d! + e! + f!"""
    l = []
    while 1:
        d = n % 10
        n //= 10
        l.append(d)
        if n == 0:
            break

    return factorial_sum_tup(tuple(sorted(l)))


def main():
    # --- main ---
    MAX_LIM = 1000000

    uniq_chain_len = [-1 for i in range(MAX_LIM * 10)]  # uniq_chain_len initialization

    # preset all known cycles
    uniq_chain_len[1] = 1  # 1 --> (1)
    uniq_chain_len[2] = 1  # 2 --> (2)
    uniq_chain_len[145] = 1  # 145 --> (145)
    uniq_chain_len[169] = uniq_chain_len[363601] = uniq_chain_len[1454] = 3  # 169 --> 363601 --> 1454 --> (169)
    uniq_chain_len[871] = uniq_chain_len[45361] = 2  # 871 --> 45361 --> (871)
    uniq_chain_len[872] = uniq_chain_len[45362] = 2  # 872 --> 45362 --> (872)
    cnt = 0
    for i in range(MAX_LIM):
        n = i
        len_uniq = 0
        while 1:
            # print(n, len_uniq)
            if n < len(uniq_chain_len) and uniq_chain_len[n] != -1:
                len_uniq += uniq_chain_len[n]
                break
            if len_uniq > 60:
                break
            n = factorial_sum(n)
            len_uniq += 1

        if i < len(uniq_chain_len) and uniq_chain_len[i] != -1:
            uniq_chain_len[i] = len_uniq
        if len_uniq == 60:
            print(i, len_uniq)
            cnt += 1
        # print(i, len_uniq)
    print("------")
    print(cnt)


if __name__ == "__main__":
    main()