Project Euler Solution 34: Digit factorials

Problem 34: Digit factorials is another digit-sum problem.

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: As 1! = 1 and 2! = 2 are not sums they are not included.

I have solved this problem in the functional style. First I wrote a factorial function which uses the binary reduction that we had use in a previous problem. In order to not waste time on repeated evaluations, I wrap it in a cache.

@functools.cache
def factorial(n: int) -> int:
    return functools.reduce(lambda a, b: a * b, range(1, n + 1), 1)

Then it becomes pretty easy to write a function that computes the sum of the digit factorials. This doesn't need a cache because we only compute each number once.

def digit_factorial_sum(n: int) -> int:
    return sum(factorial(int(c)) for c in str(n))

There is no upper limit given, therefore we need to compute it. Just like in Solution 30: Digit fifth powers there is a natural limit when multiples of 9! cannot exceed a number with a given number of digits.

def upper_limit() -> int:
    for num_digits in itertools.count(1):
        if factorial(9) * num_digits < 10**num_digits:
            return factorial(9) * num_digits + 1

With all these building blocks in place, we can write the solution as another sum over a generator expression.

def solution() -> int:
    return sum(
        number
        for number in range(3, upper_limit())
        if number == digit_factorial_sum(number)
    )

This takes 4.9 s to compute.

Here it is interesting to see that most of the problem has been solved in a function style, which might be unusual when one normally works with the procedural style.