Optimizing run time of Python solution to Project Euler Problem 34 This is a brute force solution to Project Euler Problem 34 with only 1 optimization (i.e.: caching factorials):

import time, math
start = time.time()

total = 0

# Cache factorials
factorials = [math.factorial(x) for x in xrange(0,10)]
range_end = 7 * factorials[9]

for i in range(3,range_end+1):
    number = i
    factorials_sum = 0

    while(number &gt; 0):
        digit = number % 10
        number /= 10
        factorials_sum += factorials[digit]

    if(factorials_sum == i):
        total += factorials_sum

print "Time elapsed: %5.2f" % (time.time() - start)
print total


I know it could be further optimized (f.e. by choosing numbers that the for loop could pass on. However, I would like to ask why is this algorithm running 10.3 s on my computer (2.66 GHz Intel Core 2 Duo)? Similar solutions I have found run in ~2 seconds or less. Is there any general optimization I could make?
You can shave some (minimal) time by bailing out early of your factorial sum calculation, and using the divmod operator:

while number and factorial_sum &lt;= number:
    number, digit = divmod(number, 10)
    factorial_sum += factorials[digit]


But that is still going to be fairly slow, and take several seconds to compute. If you want a quick solution, you need to stop rechecking numbers that you already know cannot fulfill the condition. This is best done checking the digits from most significant to least significant. A possible implementation using recursion would be:

factorials = [1, 1]
for j in range(2, 10):
    factorials.append(j * factorials[-1])

def factorion_sum(number, factorial_sum):
    number *= 10
    total = 0
    for digit in range(10):
        new_number = number + digit
        new_factorial_sum = factorial_sum + factorials[digit]
        if new_number == new_factorial_sum:
            total += new_number
        # If the smallest number in the next iteration exceeds
        # the next largest factorial sum, we are done here 
        if new_number*10 &lt;= new_factorial_sum + factorials[-1]:
            total += factorion_sum(new_number, new_factorial_sum)
    return total

print sum(factorion_sum(j, factorials[j]) for j in range(1, 10)


This produces the right result in a fraction of a second.