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,
44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
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?
Iterate through and record groups of '1' and '89'.
import sys, os; sys.path.append(os.path.abspath('..'))
from timer import timethis
record = {
1: set([1]),
89: set([89])
}
def get_digits(n):
digits = []
while n:
digits.append(n % 10)
n //= 10
return digits
@timethis
def solve():
cnt = 0
square = lambda i: pow(i, 2)
for i in range(1, int(1e7)+1):
j = i
js = set([i])
while True:
if j in record[1]:
record[1].update(js)
break
elif j in record[89]:
record[89].update(js)
cnt += 1
break
else:
j = sum(map(square, get_digits(j)))
js.add(j)
return cnt
solve()