Square digit chains
Problem 92
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
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?
def run(limit=10000000, searched=89):
count = 0
valid = set()
invalid = set()
for i in range(1, limit):
total = 0
n = i
tmp = set([i])
if i in valid:
count += 1
elif i in invalid:
continue
else:
while True:
for d in str(n):
square = int(d) * int(d)
total += square
if total in valid:
count += 1
for x in list(tmp):
valid.add(x)
break
elif total in invalid:
for x in list(tmp):
invalid.add(x)
break
else:
tmp.add(total)
if total == 1:
for x in list(tmp):
invalid.add(x)
break
elif total == searched:
for x in list(tmp):
valid.add(x)
count += 1
break
else:
n = total
total = 0
return count