forked from TheAlgorithms/Python
-
Notifications
You must be signed in to change notification settings - Fork 0
/
sol1.py
85 lines (67 loc) · 2.28 KB
/
sol1.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
"""
Project Euler Problem 092: https://projecteuler.net/problem=92
Square digit chains
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?
"""
DIGITS_SQUARED = [digit**2 for digit in range(10)]
def next_number(number: int) -> int:
"""
Returns the next number of the chain by adding the square of each digit
to form a new number.
For example, if number = 12, next_number() will return 1^2 + 2^2 = 5.
Therefore, 5 is the next number of the chain.
>>> next_number(44)
32
>>> next_number(10)
1
>>> next_number(32)
13
"""
sum_of_digits_squared = 0
while number:
sum_of_digits_squared += DIGITS_SQUARED[number % 10]
number //= 10
return sum_of_digits_squared
CHAINS = {1: True, 58: False}
def chain(number: int) -> bool:
"""
The function generates the chain of numbers until the next number is 1 or 89.
For example, if starting number is 44, then the function generates the
following chain of numbers:
44 → 32 → 13 → 10 → 1 → 1.
Once the next number generated is 1 or 89, the function returns whether
or not the next number generated by next_number() is 1.
>>> chain(10)
True
>>> chain(58)
False
>>> chain(1)
True
"""
if number in CHAINS:
return CHAINS[number]
number_chain = chain(next_number(number))
CHAINS[number] = number_chain
return number_chain
def solution(number: int = 10000000) -> int:
"""
The function returns the number of integers that end up being 89 in each chain.
The function accepts a range number and the function checks all the values
under value number.
>>> solution(100)
80
>>> solution(10000000)
8581146
"""
return sum(1 for i in range(1, number) if not chain(i))
if __name__ == "__main__":
import doctest
doctest.testmod()
print(f"{solution() = }")