Euler problem 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.

solution:

Wikipedia,

A factorion is a natural number that equals the sum of the factorials of its decimal digits. For example, 145 is a factorion because 1! + 4! + 5! = 1 + 24 + 120 = 145.

There are just four factorions and they are 1, 2, 145 and 40585 (sequence A014080 in OEIS).

analyse:

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

performance improvements:

1) According wiki the greatest factorion is 40585         // 1034 -> 15 ms.

2) Add Cache for Fac 0 to 9                                      //     15 ->  3 ms.

Problem34 =       40730 elapsed time:    3 ms. Test Passed.