Python Implementation of Problem 92
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 92
I had to approach this by modifying the factors function from p0003, but it seemed to work fairly well.
Problem:
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?
1"""
2Project Euler Problem 92
3
4I had to approach this by modifying the factors function from p0003, but it
5seemed to work fairly well.
6
7Problem:
8
9A number chain is created by continuously adding the square of the digits in a
10number to form a new number until it has been seen before.
11
12For example,
13
1444 → 32 → 13 → 10 → 1 → 1
1585 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
16
17Therefore any chain that arrives at 1 or 89 will become stuck in an endless
18loop. What is most amazing is that EVERY starting number will eventually arrive
19at 1 or 89.
20
21How many starting numbers below ten million will arrive at 89?
22"""
23from typing import MutableMapping
24
25from .lib.iters import digits
26
27
28def f(n: int, cache: MutableMapping[int, int]) -> int:
29 if n in cache:
30 return cache[n]
31 result = sum(x**2 for x in digits(n))
32 cache[n] = result
33 return result
34
35
36def main() -> int:
37 answer = 0
38 cache: MutableMapping[int, int] = {}
39 for x in range(2, 10000000):
40 while x not in (1, 89):
41 x = f(x, cache)
42 if x == 89:
43 answer += 1
44 return answer