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,
\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.207s
user 0m23.032s
sys 0m0.173s