Optimizing run time of Python solution to Project Euler Problem 34

Question

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 > 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?

Answer 1

Micro-optimisations

As a reference for later, on the computer I am using, your original code ran in 5.55 seconds.

The precomputation of factorial is a nice touch but you can make it even more useful. Indeed, instead of going through the "hassle" of decomposing number and computing the factorial for each "decomposed" number, you can use the fact that the conversion from int to string pretty much gives you what you want (and is expected to be optimised). Once it is done, you just need to compute the factorial for each character. Writing the precomputation of the factorial for the different characters gives, with a dict comprehension :

fact = {c: math.factorial(int(c)) for c in string.digits}

while the actual computing of the factorial sum, with geenrator expression is just :

sum(fact[c] for c in str(i))

This leads to some pretty concise and efficient code to be written :

fact = {c: math.factorial(int(c)) for c in string.digits}
range_end = 7 * fact['9']

for i in range(3,range_end+1):
    if (i == sum(fact[c] for c in str(i))):
        total += i

This code runs on 3.20 seconds on my computer : almost twice faster.

Things can be written in an even more concise and efficient way (it reads as maths):

fact = {c: math.factorial(int(c)) for c in string.digits}
range_end = 7 * fact['9']
total = sum(i for i in range(3,range_end+1) if (i == sum(fact[c] for c in str(i))))

And this runs in 2.83 seconds : getting close to the 50% ratio.

About code organisation

You probably won't care too much about this kind of stuff for project euler scripts* but it can be quite convenient to define functions/classes in a module that you can later on import. If you do so, it is quite cool to have the import as lightweight as possible, for instance, you don't want to go through computations when you import the code. In order to do so, the usage is to put the code "actually doing stuff" behind an "if main guard" :

pass # this will be done when your code is imported
if __name__ == "__main__":
    pass # but this will be done only when your code is actually run

• Actually, the more you go through project euler problems, the more you'll see it can be quite convenient to build a toolbox with things like Eratosthene's sieve and other cool algorithms.

New algorithm

You can use a completely different algorithm : this seems to run really fast :

import itertools, string, math

fact = {c: math.factorial(int(c)) for c in string.digits}
dict_sum = {}
for nb_dig in range(2, 7+1):
    for l in itertools.combinations_with_replacement(string.digits, nb_dig):
        dict_sum.setdefault(sum(fact[c] for c in l), []).append(list(l))
print(sum(n for n, l in dict_sum.items() if sorted(str(n)) in l))

Basically, the point is to construct a dictionnary mapping integers to the different combinations leading to that integer once the factorial of digits is applied. For instance :

6 -> [['2', '2', '2'], ['0', '0', '2', '2'], ['0', '1', '2', '2'], ['1', '1', '2', '2'], ['0', '0', '0', '0', '2'], ['0', '0', '0', '1', '2'], ['0', '0', '1', '1', '2'], ['0', '1', '1', '1', '2'], ['1', '1', '1', '1', '2'], ['0', '0', '0', '0', '0', '0'], ['0', '0', '0', '0', '0', '1'], ['0', '0', '0', '0', '1', '1'], ['0', '0', '0', '1', '1', '1'], ['0', '0', '1', '1', '1', '1'], ['0', '1', '1', '1', '1', '1'], ['1', '1', '1', '1', '1', '1']]
145 -> [['0', '4', '5'], ['1', '4', '5'], ['0', '3', '3', '3', '3', '5'], ['1', '3', '3', '3', '3', '5'], ['0', '4', '4', '4', '4', '4', '4'], ['1', '4', '4', '4', '4', '4', '4']]
146 -> [['2', '4', '5'], ['0', '0', '4', '5'], ['0', '1', '4', '5'], ['1', '1', '4', '5'], ['2', '3', '3', '3', '3', '5'], ['0', '0', '3', '3', '3', '3', '5'], ['0', '1', '3', '3', '3', '3', '5'], ['1', '1', '3', '3', '3', '3', '5'], ['2', '4', '4', '4', '4', '4', '4']]
40585 -> [['0', '4', '5', '5', '8'], ['1', '4', '5', '5', '8']]
2177280 -> [['9', '9', '9', '9', '9', '9']]

The trick is that because we only consider "ordered" permutations, we don't have that many cases to handle : we consider 19437 permutations (instead of 9999999 integers) leading to 8500 distinct integers.

Then for each integer, we consider if it is a valid number by checking that its corresponding decomposition is in the associated list.

The point of using a dict instead of checking each number as we go is just to make debugging easier for me but also to try to limit the number of time we perform the same operations by grouping them : sorted(str(n)) is not called as often as it would otherwise. However, I have done any profiling as it was fast enough for me.

Answer 2

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 <= 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 <= 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.

Answer 3

I assume there could be 1 more further checking on the first digit of sum of the factorials. which is less compute consuming but might increase the search a bit.

like 135 should check d1(1!)+d1(3!)+d1(5!)==5