Project Euler Solution 74: Digit factorial chains

Project Euler Problem 74: Digit factorial chains brings us back to playing with digits of numbers.

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 non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

This can be solved straightforwardly. First we need to have a factorial function for the digits. We expect it to be called with the values from 0 to 9, so we can happily cache all of them.

@functools.cache
def factorial(number: int) -> int:
    result = 1
    for k in range(2, number + 1):
        result *= k
    return result

The next numbers are likely going to occur again and again. Therefore we also cache them. In order not to overwhelm the memory, I set a limit for it.

@functools.lru_cache(10_000_000)
def factorial_digit_sum(number: int) -> int:
    return sum(factorial(int(digit)) for digit in str(number))

And then we just have to iterate through all numbers. We can already stop after more than 60 iterations because we only care for the numbers where the length is exactly 60 elements.

def solution() -> int:
    result = 0
    for number in range(1_000_000):
        steps = [number]
        for iteration in range(60):
            new_number = factorial_digit_sum(steps[-1])
            if new_number in steps:
                if iteration == 59:
                    result += 1
                break
            steps.append(new_number)
    return result

With this we get the solution within 11 s, so that is fast enough for the rules of the problem. Without the cache on the factorial, it would take 12 s. Without the cache on the factorial digit sum, it would take 45 s.

One could try to squeeze out a bit more by trying to derive partial sequence lengths from the sequences that one has built. Also one can further look at the numbers and realize that all permutations of a number have the same digit factorial sum and that one can exchange all 0 and 1 in the digits as 0! = 1 and 1! = 1.