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.