(17 votes, average: 5.00 out of 5)

Project Euler 34: Find the sum of all numbers which are equal to the sum of the factorial of their digits

Project Euler 34 Problem Description

Project Euler 34: 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.

Analysis

These type of numbers are referred to as factorions and it’s easy to learn that only 4 exist: 1, 2, 145 & 40585. The problem asks us to ignore 1 & 2 so the answer to this problem should become 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 (from Wikipedia: Factorion):

If n is a natural number of d digits that is a factorion, then 10d − 1 ≤ n ≤ 9!d. This fails to hold for d ≥ 8 thus n has at most 7 digits, and the first upper bound is 9,999,999. But the maximum sum of factorials of digits for a 7 digit number is 9!*7 = 2,540,160 establishing the second upper bound.

All factorials of digits at least 5 have the factors 5 and 2 and thus end on 0. Let 1abcdef denote our 7 digit number. If all digits a-f are all at least 5, the sum of the factorials – which is supposed to be equal to 1abcdef – will end on 1 (coming from the 1! in the beginning).

This is a contradiction to the assumption that f is at least 5. Thus, at least one of the digits a-f can be at most 4, which establishes 1!+4!+5*9!=1814425 as fifth upper bound. Assuming n is a 7 digit number, the second digit is at most 8. There are two cases: If a is at least 5, by the same argument as above one of the remaining digits b-f has to be at most 4. This implies an upper bound (since a is at most 8) of 1!+8!+4!+4*9!= 1491865, a contradiction to a being at least 5. Thus, a is at most 4 and the sixth upper bound is 1499999.

```#Solution for Project Euler 34
from Euler import sof_digits
s = sum(n for n in range(10, 1500000) if n == sof_digits(n))
print "Project Euler 34 Solution =", s
```

HackerRank version

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. They provide a query, 10≤N≤105, and we report the total of all numbers less than N that divide the sum of the factorial of their digits.

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

```fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
```
This program and method
solves all test cases for
Project Euler 34 on HackerRank

Project Euler 34 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 34 Solution Python 2.7 source.

Afterthoughts

Project Euler 34 Solution last updated