Project Euler Problem 34 Solution

Project Euler Problem 34 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

At first read this problem appears to describe a boundless search for numbers which sum to the factorial of their digits. But, after some quick research, it appears that these type of numbers are referred to as factorions and that only 4 exist: 1, 2, 145 & 40585. This problem asks us to ignore 1 & 2 so the answer should be obvious.

But, let’s write a program anyway to search for factorions. As usual, when writing a brute force search algorithm, we must first determine our bounds. The lower bound is 10 because single digit candidates are to be ignored. The upper bound we discover as follows (paraphrased from an archived discussion on Wikipedia: Factorion):

If n is a natural number with d digits that is a factorion, then $10^{d-1}\le n\le d\cdot 9!$. For $d\ge 8$ this inequality fails to hold, so $n$ has at most seven digits.

Therefore, the maximum possible factorion is less than $9!\cdot 7 = 2,540,160$, setting an upper bound for our search.

Now, going further, since no number larger than 2,540,160 is possible, the first digit of our upper bound can be at most 2. Therefore, we can redefine our upper bound to $2!+6\cdot 9!= 2,177,282$, which is sufficiently restrictive.

Let's analyze the inequalities: The left side $10^{d-1}$ is the smallest $d$-digit number. The right side $d\cdot 9!$ is the maximum possible sum of factorials for $d$ digits, since 9! is the largest single-digit factorial.

For $d\ge 8$, this inequality becomes impossible because the smallest 8-digit number is $10^7 = 10,000,000$ and the maximum sum of factorials would be $8\cdot 9! = 8\cdot 362,880 = 2,903,040$, i.e., $10,000,000\le 2,903,040$ is false.

The final refinement notes that since $2,540,160$ is our upper bound because the first digit can't be larger than 2. Therefore, the maximum possible sum would be: $2! + 6\cdot 9!$ (where $6\cdot 9!$ represents the maximum possible contribution from the remaining 6 digits). This gives us $2 + 6\cdot 362,880 = 2,177,282$ as a tighter upper bound.

An obvious approach

Having a list of factorials of the numbers 0 through 9 saves having to calculate the factorials of the individual digits each time.

f = {'0':1, '1':1, '2':2, '3':6, '4':24, '5':120, '6':720, '7':5040, '8':40320, '9':362880}

A lambda function calculates the sum of each digit's factorial quickly.

sdf = lambda n: sum(factorial[d] for d in str(n))
is_factorion = lambda n: n==sdf(n)

These two Python statements setup the requirements to solve the Project Euler and the HackerRank problem.

print(sum(n for n in range(10, 2177283) if is_factorion(n))

print(sum(i for i in range(10, int(input())) if sdf(i)%i == 0))

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 34

HackerRank Project Euler 34 didn’t have much liberty in expanding this problem, so they created a version still requiring the sum of the factorial–digits, but with a twist. They provide a query, 10 ≤ N ≤ 10⁵, and we find the total of all numbers less than N that divide the sum of the factorial of their digits.

Last Word

• Since the set of factorions is finite, a brute-force approach is fully viable. This solution takes a couple seconds.
• Reference: The On–Line Encyclopedia of Integer Sequences (OEIS) A014080: Factorions: equal to the sum of the factorials of their digits in base 10.