Project Euler Problem #34:

Problem #34 is one of the many Project Euler problems that involves factorials. It involves an obscure type of number called an factorion. Factorions are numbers for which the sum of the factorials of the digits is equal to the number itself. The question reads:

Project Euler Problem #34: Digit factorials
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.

Once again, my solution for this problem involves iterative brute force.

Solution #1: Brute Force Approach

First we calculate an upper bound for the maximum number which is equal to the sum of the factorials of its digits. Clearly the sum of the factorials of the digits of a number is maximized when all of the digits are 9 for a fixed number of digits. Consequently, it suffices to find the minimum number of digits n for which a number formed with n digits of 9 is greater than the product of 9! and n. This can be done easily without much inefficiency.

Once the upper bound is calculated, we simply check every number less than the upper bound for this property. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #34
 '''

 import time

 def factorial(n):
     total = 1
     for c in range(2,n+1):
         total*=c
     return total

 def projectEulerProblemThirtyFour(n):
     factorials = []
     for x in range(10):
         factorials.append(factorial(x))
     a = 1
     while((10*a) - 1 < factorials[n]*a):
         a+=1
     total = 0
     final = factorials[n] * a
     for c in range(3,final+1):
         myString = str(c)
         subTotal = 0
         for x in myString:
             subTotal+=factorials[int(x)]
         if(subTotal==c):
             total+=c
     return total

 start = time.time()
 print projectEulerProblemThirtyFour(9)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 40730
 --- 6.35254812241 seconds ---

 for input of n = 9
 '''

This solution clearly isn’t very efficient as it does not filter the numbers that need to be checked at all. However, it does run in under 10 seconds, which is better than I can say for some of my later solutions. I may come back to this problem at some point to search for a more efficient solution.

Thanks for reading!