project euler problem 074 https projecteuler netproblem74 the number 145 is well known for the property that the sum of the factorial of its digits is equal to 145 1 4 5 1 24 120 145 perhaps less well known is 169 in that it produces the longest chain of numbers that link back to 169 it turns out that there are only three such loops that exist 169 363601 1454 169 871 45361 871 872 45362 872 it is not difficult to prove that every starting number will eventually get stuck in a loop for example 69 363600 1454 169 363601 1454 78 45360 871 45361 871 540 145 145 starting with 69 produces a chain of five nonrepeating terms but the longest nonrepeating chain with a starting number below one million is sixty terms how many chains with a starting number below one million contain exactly sixty nonrepeating terms solution approach this solution simply consists in a loop that generates the chains of non repeating items using the cached sizes of the previous chains the generation of the chain stops before a repeating item or if the size of the chain is greater then the desired one after generating each chain the length is checked and the counter increases function to perform the sum of the factorial of all the digits in number digitfactorialsum69 0 traceback most recent call last typeerror parameter number must be int digitfactorialsum1 traceback most recent call last valueerror parameter number must be greater than or equal to 0 digitfactorialsum0 1 digitfactorialsum69 363600 converts number in string to iterate on its digits and adds its factorial returns the number of numbers below numberlimit that produce chains with exactly chainlength non repeating elements solution10 0 1000 traceback most recent call last typeerror parameters chainlength and numberlimit must be int solution10 1000 0 traceback most recent call last typeerror parameters chainlength and numberlimit must be int solution0 1000 traceback most recent call last valueerror parameters chainlength and numberlimit must be greater than 0 solution10 0 traceback most recent call last valueerror parameters chainlength and numberlimit must be greater than 0 solution10 1000 26 the counter for the chains with the exact desired length the cached sizes of the previous chains the temporary set will contain the elements of the chain stop computing the chain when you find a cached size a repeating item or the length is greater then the desired one if chain contains the exact amount of elements increase the counter function to perform the sum of the factorial of all the digits in number digit_factorial_sum 69 0 traceback most recent call last typeerror parameter number must be int digit_factorial_sum 1 traceback most recent call last valueerror parameter number must be greater than or equal to 0 digit_factorial_sum 0 1 digit_factorial_sum 69 363600 converts number in string to iterate on its digits and adds its factorial returns the number of numbers below number_limit that produce chains with exactly chain_length non repeating elements solution 10 0 1000 traceback most recent call last typeerror parameters chain_length and number_limit must be int solution 10 1000 0 traceback most recent call last typeerror parameters chain_length and number_limit must be int solution 0 1000 traceback most recent call last valueerror parameters chain_length and number_limit must be greater than 0 solution 10 0 traceback most recent call last valueerror parameters chain_length and number_limit must be greater than 0 solution 10 1000 26 the counter for the chains with the exact desired length the cached sizes of the previous chains the temporary set will contain the elements of the chain stop computing the chain when you find a cached size a repeating item or the length is greater then the desired one if chain contains the exact amount of elements increase the counter
from math import factorial

DIGIT_FACTORIAL: dict[str, int] = {str(digit): factorial(digit) for digit in range(10)}


def digit_factorial_sum(number: int) -> int:
    
    if not isinstance(number, int):
        raise TypeError("Parameter number must be int")

    if number < 0:
        raise ValueError("Parameter number must be greater than or equal to 0")

    
    return sum(DIGIT_FACTORIAL[digit] for digit in str(number))


def solution(chain_length: int = 60, number_limit: int = 1000000) -> int:
    

    if not isinstance(chain_length, int) or not isinstance(number_limit, int):
        raise TypeError("Parameters chain_length and number_limit must be int")

    if chain_length <= 0 or number_limit <= 0:
        raise ValueError(
            "Parameters chain_length and number_limit must be greater than 0"
        )

    
    chains_counter = 0
    
    chain_sets_lengths: dict[int, int] = {}

    for start_chain_element in range(1, number_limit):
        
        chain_set = set()
        chain_set_length = 0

        
        
        chain_element = start_chain_element
        while (
            chain_element not in chain_sets_lengths
            and chain_element not in chain_set
            and chain_set_length <= chain_length
        ):
            chain_set.add(chain_element)
            chain_set_length += 1
            chain_element = digit_factorial_sum(chain_element)

        if chain_element in chain_sets_lengths:
            chain_set_length += chain_sets_lengths[chain_element]

        chain_sets_lengths[start_chain_element] = chain_set_length

        
        if chain_set_length == chain_length:
            chains_counter += 1

    return chains_counter


if __name__ == "__main__":
    import doctest

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