Project Euler Problem 74 Solution: Digit Factorial Chains

Project Euler Problem 74 Statement

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:

$$\begin{align} &169 \to 363601 \to 1454 \to 169\\ &871 \to 45361 \to 871\\ &872 \to 45362 \to 872 \end{align}$$

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,

$$\begin{align} &69 \to 363600 \to 1454 \to 169 \to 363601 (\to 1454)\\ &78 \to 45360 \to 871 \to 45361 (\to 871)\\ &540 \to 145 (\to 145) \end{align}$$

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?

Solution

Project Euler problem 74 deals with generating factorial chains—sequences where each number is replaced by the sum of the factorials of its digits, continuing this process until a loop is found. The primary objective is to determine the length of these chains before they start repeating.

Some setup optimizations

Define a list of factorials for the digits 0 through 9, which allows quick lookups when computing the sum of factorials of a number's digits.
A cache (dictionary) is seeded with known chain lengths for specific numbers to avoid recalculating chains that are already known to loop. This also serves for caching new chains found,
The sdf() function returns the sum of each digit's factorial for a given number.

Find chains

The heart of this solution is shouldered by the compute_chain_length() function, which returns a cached result if it exists, or otherwise recursively computes the chain length by calling itself with the factorial digit sum of the current number and then incrementing the chain length by one. This newly computed chain length is stored in the cache to speed up subsequent lookups.

Simple execution

We start by considering each test case. The code reads two integers, $N$ and $L$, and checks every number from 0 to $N$ to find which chain length matches $L$. It joins such numbers in a space-separated string for output, or prints -1 if no numbers match the desired chain length. Trying filter as I think it's more readable.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 74

HackerRank Project Euler 74: For a given length $L$ and limit $N$ print all the integers $\le N (10\le N\le 1000000)$ which have chain length $L (1\le L\le 60)$. Where there are no such numbers for a given $L$, print -1

Python Source Code

f = {'0':1, '1':1, '2':2, '3':6, '4':24, '5':120, '6':720, '7':5040, '8':40320, '9':362880}
chain_cache = {1:1, 2:1, 145:1, 40585:1, 169:3, 363601:3, 1454:3, 871:2, 45361:2, 872:2, 45362:2}
sdf = lambda n: sum(f[d] for d in str(n))

def find_chain_length(n):
    try:
        return chain_cache[n]
    except:
        chain_length = find_chain_length(sdf(n)) + 1
        chain_cache[n] = chain_length
        return chain_length

for _ in range(int(input())):
    N, L = map(int, input().split())
    q = [*filter(lambda n: find_chain_length(n) == L, range(N + 1))] or [-1]
    print(*q)