# from euler import *
from math import factorial
from itertools import permutations
from time import time,clock
t = time()

answer = 0
fac_d = {}

def fac_sum(n):
    if n in fac_d:
        return fac_d[n]
    else:
        sum = 0
        for c in (str(n)):
            sum += factorial(int(c))
        fac_d[n] = sum
        return sum

for i in (range(1000000)):
    chain_length = 1
    sums = set()
    sums.add(i)
    sum = fac_sum(i)
    while sum not in sums:
        sums.add(sum)
        chain_length += 1
        sum = fac_sum(sum)
    if chain_length == 60:
        print i
        answer += 1
        
print answer              
print 'time', time()-t


# 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?
