sol1.py

"""
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= [sum(int(c, 10) **2forcini.__str__()) foriinrange(100000)]


defnext_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
whilenumber:
# Increased Speed Slightly by checking every 5 digits together.
sum_of_digits_squared+=DIGITS_SQUARED[number%100000]
number//=100000

returnsum_of_digits_squared


# There are 2 Chains made,
# One ends with 89 with the chain member 58 being the one which when declared first,
# there will be the least number of iterations for all the members to be checked.

# The other one ends with 1 and has only one element 1.

# So 58 and 1 are chosen to be declared at the starting.

# Changed dictionary to an array to quicken the solution
CHAINS: list[bool|None] = [None] *10000000
CHAINS[0] =True
CHAINS[57] =False


defchain(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
 """

ifCHAINS[number-1] isnotNone:
returnCHAINS[number-1] # type: ignore[return-value]

number_chain=chain(next_number(number))
CHAINS[number-1] =number_chain

whilenumber<10000000:
CHAINS[number-1] =number_chain
number*=10

returnnumber_chain


defsolution(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
 """
foriinrange(1, number):
ifCHAINS[i] isNone:
chain(i+1)

returnCHAINS[:number].count(False)


if__name__=="__main__":
importdoctest

doctest.testmod()
print(f"{solution() =}")