58 lines
1.1 KiB
Python
58 lines
1.1 KiB
Python
# 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?
|
|
|
|
from numpy import zeros
|
|
|
|
from projecteuler import timing
|
|
|
|
|
|
N = 10000000
|
|
chains = zeros(N)
|
|
|
|
|
|
def chain(n):
|
|
tmp = 0
|
|
|
|
if n == 1:
|
|
return 1
|
|
|
|
if n == 89:
|
|
return 89
|
|
|
|
if chains[n] != 0:
|
|
return chains[n]
|
|
|
|
while n > 0:
|
|
digit = n % 10
|
|
tmp += digit ** 2
|
|
n //= 10
|
|
|
|
return chain(tmp)
|
|
|
|
|
|
@timing
|
|
def p092():
|
|
count = 0
|
|
|
|
for i in range(1, N):
|
|
chains[i] = chain(i)
|
|
|
|
if chains[i] == 89:
|
|
count += 1
|
|
|
|
print('Project Euler, Problem 92')
|
|
print(f'Answer: {count}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p092()
|