Project Euler 34 - digit factorials

Question

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.

I can't figure out a fair way to optimize the upper bound from the information given in the question. I went on the PE forum and found many people setting the upper bound to 50000 because they knew that would be large enough after testing. This doesn't seem fair to me; I want to set the bound based on the information in the question. Right now it runs in around 20 seconds.

EDIT: I'm not looking for a mathematical algorithm. I'm looking for ways to make this code faster.

from math import factorial as fact
from timeit import default_timer as timer

start = timer()
def findFactorialSum():
    factorials = [fact(x) for x in range(0, 10)] # pre-calculate products
    total_sum = 0
    for k in range(10, fact(9) * 7): # 9999999 is way more than its fact-sum
        if sum([factorials[int(x)] for x in str(k)]) == k:
            total_sum += k

    return total_sum

ans = findFactorialSum()
elapsed_time = (timer() - start) * 1000 # s --> ms

print "Found %d in %r ms." % (ans, elapsed_time)

Answer 1

I'm not aware of any mathematical way to establish the upper bound for the search space (I used the same upper limit as you did). However, there are some optimizations you can make:

1. Use integer math throughout instead of converting to a string, extracting the digits, then converting back to an integer. On my PC, your algorithm ran in approximately 6200ms. Using integer math as follows (there may be a more Pythonic way to do this; my code is a direct transliteration of C++ that I used), it ran in approximately 1600ms -- almost 4 times as fast:

   def findFactorialSum():
       factorials = [fact(x) for x in range(0, 10)] # pre-calculate products
       total_sum = 0
       for k in range(10, fact(9) * 7): # 9999999 is way more than its fact-sum
           tmp = k
           total = 0
           while tmp > 0:
               total += factorials[tmp % 10]
               tmp //= 10
   
           if total == k:
               total_sum += k
   
       return total_sum
   

   (For my curiosity, I also tried it with the '/' operator instead of the '//' operator, and consistently got 100ms longer run times with the former.)

2. You're doing an exhaustive search of the numbers from [10...7*9!] to see which ones meet the problem criteria. You can eliminate a large proportion of those numbers:

   Hint 1:

   No 2-digit number can have a digit >= 5. This is because 5! == 120, so any 2-digit number with a 5 (or higher) in it will automatically have a 3-digit (or longer) sum. You can extend this rule for 3-, 4- and 5- digit numbers.

   Hint 2:

   Extending Hint 1: No 3-digit number can have more than one 7 in it. 7! is 720, so if you have two 7s, you have 1440, a 4-digit number. There are a few more opportunities like this to eliminate numbers to check

   Hint 3:

   Think of the number 145 given in the problem; since you know that this works, there's no need to check numbers that are a permutations of its digits: 154, 415, 451, 514, 541. The trick here is to look at the problem the other way around: instead of finding numbers whose Sum of Factorials of Digits equals the original number, find an ordered sequence of digits whose Sum of Factorials can be split into a sequence of digits, sorted, and that compares equal to the original sequence.

Answer 2

This is much faster than both of your solutions(~50 ms compared to 5 and 13 seconds) jshuaf when you initialized the factorial values try using a dictionary instead of a list also allows me to use str keys and get int values,

import math

def problem34():
    total=0
    factorials={}
    for i in xrange(10):
        factorials[str(i)]=math.factorial(i)    
    for i in xrange(3,50000):
        factorial_sum=0
        for j in str(i):
            factorial_sum+=factorials[j]
        if factorial_sum==i:
            total+=factorial_sum
    return total