from pylab import *

%matplotlib inline

factorial(10)

def factorial(n):
    if n==0 or n==1:
        return 1
    else:
        return n * fact(n-1)

[factorial(i) for i in range(0, 10)]

def factorial_algorithm(n):
    return sum([factorial(int(digit)) for digit in str(n)])

factorial_algorithm(145)

n = arange(200)

plot(n, list(map(factorial_algorithm, n)))
plot(n, n, 'r', lw=3)

plot(n, list(map(factorial_algorithm, n)))
plot(n, n, 'r', lw=3)
ylim(0, n.max())

factorial_algorithm(40585)

double_algorithm = lambda n: factorial_algorithm(factorial_algorithm(n)) 

plot(n, list(map(factorial_algorithm, n)), label='simple')
plot(n, list(map(double_algorithm, n)), label='double')
legend()

factorial_algorithm(199)

factorial_algorithm(725761)

def chain_length(n):
    chain = [n]
    iteration = factorial_algorithm(n)
    while iteration not in chain:
        chain.append(iteration)
        iteration = factorial_algorithm(iteration)
    return chain

from IPython.html.widgets import interact

interact(lambda n: print(chain_length(n)),
         n=(0, 1000))

factorial_algorithm(1454)

n = arange(1000)

chain_lengths = [len(chain_length(i)) for i in n]
plot(n, chain_lengths)

%time chain_lengths = [len(chain_length(i)) for i in n]

def first_sieve():
    n = arange(1000000)
    print(n[array(list(map(factorial_algorithm, n))) == n])

%time first_sieve()

class chain_length_memoized():
    def __init__(self):
        self.lookup_table = {1:0,
                             2:0,
                             145:0,
                             40585:0,
                             871:1,
                             45361:1,
                             872:1,
                             45362:1,
                             169:2,
                             363601:2,
                             1454:2}
        
    def compute_chain_length(self, n):
        if n in self.lookup_table:
            return 1 + self.lookup_table[n]
        else:
            iteration = factorial_algorithm(n)
            self.lookup_table[n] = self.compute_chain_length(iteration)
            return 1 + self.lookup_table[n]


clm = chain_length_memoized()

clm.compute_chain_length(0)

z = chain_length(0)
print(z, len(z))

for i in range(1000000):
    if clm.compute_chain_length(i) == 60:
        print(i)

%time len([i for i in range(1000000) if clm.compute_chain_length(i) == 60])