Problem 034


Project Euler

Digit factorials

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.


Since no mention of what the upper limit would be for this search, the first thing is to find this upper limit. Notice the following:
  • 9! = 362880
  • 9! * 5 = 1814400 (5 represents the number of digits)
  • 9! * 6 = 2177280
  • 9! * 7 = 2540160
  • 9! * 8 = 2903040 (There is no way to get this.)

Therefore, we will stop at 10 million. Before start doing the search, calculate factorial 1 to 9 and store them in an array for fast access and avoid calculating each one over and over again. Now, search from 10 to 10 million and check if the sum of the factorial of the digit equal to the number itself.

Advertisements