## Project Euler & HackerRank Problem 34 Solution

##### Digit factorials

by {BetaProjects} | MAY 17, 2009 | Project Euler & HackerRank### 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. The problem asks us to ignore 1 & 2 so the answer to this problem 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 (from an archived discussion on Wikipedia: Factorion):

If

nis a natural number ofddigits that is a factorion, then 10^{d−1}≤n≤ 9!d. This fails to hold ford≥ 8 thusnhas at most seven digits, and the first upper bound is 9,999,999. But the maximum sum of factorials of digits for a seven–digit number is 9!*7 = 2,540,160 establishing the second upper bound.Going further, since no number bigger than 2540160 is possible, the first digit of a seven-digit number can be at most 2. Thus, only six positions can range up until 9 and 2!+6*9!= 2177282 becomes a third upper bound. This implies, if n is a seven-digit number, either the second digit is 0 or 1 or the first digit is 1. If the first digit is 2 and thus the second digit is 0 or 1, the numbers are limited by 2!+1!+5*9! = 1814403—a contradiction to the first digit being 2. Thus, a seven-digit number can be at most 1999999, establishing our fourth upper bound.

#### Simple solution

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

`fact = {'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(fact[c] for c in str(n))`

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

##### Project Euler

`print sum(n for n in range(10, 2000000) if n == sfd(n))`

##### HackerRank

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

#### HackerRank version

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^{5}, and we find the total of all numbers less than *N* that divide the sum of the factorial of their digits.

### Python Source Code

### Last Word

- This is a finite set of numbers and therefore a brute force solution is completely acceptable. As long as it runs under a minute no further optimization is necessary.
- Reference: The On–Line Encyclopedia of Integer Sequences (OEIS) A014080: Factorians: equal to the sum of the factorials of their digits in base 10.