# 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:

$\begin{split} 9! &= 362880 \\ 6 \times 9! &= 2177280 \mbox{ (a } 7 \mbox{-digit number)} \\ 7 \times 9! &= 2540160 \mbox{ (a } 7 \mbox{-digit number)} \\ 8 \times 9! &= 2903040 \mbox{ (a } 7 \mbox{-digit number)}\end{split}$

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

solutions.problem34.solve()