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 ≤ n ≤ 9!d. For d ≥ 8 this inequality fails to hold, so n has at most seven digits.

Therefore, the maximum possible factorion is less than 9!*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*9!= 2,177,282, which is sufficiently restrictive.

Simple solution

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

factorial = {'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 the factorial digits quickly.

sfd = lambda n: sum(factorial[d] for d in str(n))
is_factorion = lambda n: n==sfd(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 sfd(i)%i == 0))

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 34

HackerRank 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.