project euler problem 092 https projecteuler netproblem92 square digit chains a number chain is 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 returns the next number of the chain by adding the square of each digit to form a new number for example if number 12 nextnumber will return 12 22 5 therefore 5 is the next number of the chain nextnumber44 32 nextnumber10 1 nextnumber32 13 increased speed slightly by checking every 5 digits together 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 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 nextnumber is 1 chain10 true chain58 false chain1 true 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 solution100 80 solution10000000 8581146 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 increased speed slightly by checking every 5 digits together 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 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 type ignore 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
DIGITS_SQUARED = [sum(int(c, 10) ** 2 for c in i.__str__()) for i in range(100000)]


def next_number(number: int) -> int:
    

    sum_of_digits_squared = 0
    while number:
        
        sum_of_digits_squared += DIGITS_SQUARED[number % 100000]
        number //= 100000

    return sum_of_digits_squared


CHAINS: list[bool | None] = [None] * 10000000
CHAINS[0] = True
CHAINS[57] = False


def chain(number: int) -> bool:
    

    if CHAINS[number - 1] is not None:
        return CHAINS[number - 1]  

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

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

    return number_chain


def solution(number: int = 10000000) -> int:
    
    for i in range(1, number):
        if CHAINS[i] is None:
            chain(i + 1)

    return CHAINS[:number].count(False)


if __name__ == "__main__":
    import doctest

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