Project Euler Problem 34: Digit Factorials¶
The source code for this problem can be found here.
Problem Statement¶
\(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.
Solution Discussion¶
At first, this may appear as an unconstrained search problem over the integers, however, a reasonable upper-bound becomes clear when considering the growth rate of the sum of factorials of an integer vs. the integer itself:
In particular, note that the largest \(7\)-digit number maps to \(2540160\), which while it is also a \(7\)-digit number is significantly less than the corresponding integer \(9999999\). The \(8\)-digit equivalent doesn’t even reach an \(8\)-digit factorial sum. To summarise, \(7 \times 9!\) can be considered an upper-bound in a search as anything higher can be seen to exceed the sum of the digit factorials of that number.
The question explicitly notes that \(1!\) and \(2!\) are not valid special numbers as they involve a sum of a single term. Therefore setting a lower-bound of \(10\) will skip past such invalid special numbers.
These two aspects lead to a bounded search over the range \([10, 7 \times 9!]\). While this is sufficient, we can do better.
Recall that addition over the integers is commutative. That is, the order of integers being added doesn’t affect the result (e.g. \(1 + 2 = 3 = 2 + 1\)). So, the search can be drastically sped up by only considering the digits corresponding to integers covering the range \([10, 7 \times 9!]\). In particular, search over the sets of decimal digits of lengths \(2, \dots, 7\).
The algorithm now becomes clear. For each set of digits, compute the sum of digit factorials; if this sum consists of the original candidate digits, accumulate that candidate. Return the sum of valid special numbers.
Solution Implementation¶
from itertools import combinations_with_replacement
from lib.digital import digits_of
from lib.sequence import Factorials
def solve():
""" Compute the answer to Project Euler's problem #34 """
min_digits = 2
max_digits = 7
# Avoid re-computing various digit factorials - pre-compute for all decimal digits
factorial = Factorials()
factorials = {digit: factorial[digit] for digit in range(10)}
# Perform the search over sets of decimal digits
answer = 0
for n in range(min_digits, max_digits + 1):
for digits in combinations_with_replacement(range(10), n):
fd_sum = sum([factorials[digit] for digit in digits])
if sorted(digits_of(fd_sum, base=10)) == sorted(digits):
answer += fd_sum
return answer
expected_answer = 40730
-
solutions.problem34.solve()¶ Compute the answer to Project Euler’s problem #34