Project Euler Problem 92 Solution

Question

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

443213101185891454220416375889\displaystyle \begin{aligned} & 44 \rightarrow 32 \rightarrow 13 \rightarrow 10 \rightarrow 1 \rightarrow 1 \\ & 85 \rightarrow 89 \rightarrow 145 \rightarrow 42 \rightarrow 20 \rightarrow 4 \rightarrow 16 \rightarrow 37 \rightarrow 58 \rightarrow 89 \end{aligned}

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

Python

#!/usr/bin/env python

def get_digits(n):
    return list(map(int, str(n)))

def classify(n):
    return ''.join(sorted(str(n)))

terminators = {}
def chain(start):
    n = start
    prev = None
    sequence = []
    while prev != 1 and prev != 89:
        key = classify(n)
        sequence.append(key)
        try:
            if terminators[key]:
                for number in sequence:
                    terminators[number] = True
                return True
            elif terminators[key] == False:
                for number in sequence:
                    terminators[number] = False
                return False
        except Exception as e:
            pass

        prev = n
        n = sum(d ** 2 for d in get_digits(n))

    if prev == 89:
        for number in sequence:
            terminators[number] = True
        return True
    else:
        for number in sequence:
            terminators[number] = False
        return False

def main():
    print(len([x for x in map(chain, list(range(1, 10000000))) if x]))

if __name__ == "__main__":
    main()
$ time python3 number-chain.py
real   0m23.494s
user   0m23.212s
sys    0m0.140s