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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s