Project Euler 30 -- Digit fifth powers

Here's my solution for Project Euler Problem 30. Any optimizations in time, space, or style would be greatly appreciated.

from timeit import default_timer as timer

def digit_powers(exponent):
    def power(k):
        return int(k) ** exponent
    if exponent  ms

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

In looking at your code, it seems well written and solves the problem in a straight forward manner. The one thing I would do is to remove the else after your argument check and remove a level of indent. That just helps to keep things flat... Flat is better than nested.

Now onto optimization and potentially making it more complex than it needs to be in order to make it faster. In these problems it seems like a reasonable thing to do even though....Simple is better than complex.

Here are a couple things I looked at as potential issues:

• When doing the sum(map(power, digits)), you are calculating the power of each digit many times. If this was a much more expensive calculation then only calculating 1 time is even more important.

• In this problem there is a conversion from int->str->int. If you can breakdown the digits without converting them it saves some time. It seems like a good thing to know how to do just in case your ever trying a different language where skipping those transitions may be even faster.

To address these, I did two things:

• Pre-calculate 1-9 powers and store the results in a dictionary so they don't get recalculated (Memoization). It lets me look them up very quickly without calculating each time.

• Separate the digits using math.log10 as to avoid the int->str->int conversion.

The first item is fairly straight forward, calculating for each digit:

powers = {}
for a in range(10):
    powers[a] = a ** exponent

The second part is a little trickier, what it does is uses math.log10 which gives a count of the digits, then it does a mod 10 to get the right most digit, looks up that power to add to the total and then finally does integer division to divide by 10 effectively moving the decimal place 1 position to the left (dropping the right most digit we just dealt with). This is probably a little different between Python 2/3 due to changes in int/float division. It is basically doing what you are using [x for x in str(number)] to do but without converting to string and adding the power of 5 dict lookup as it goes along:

savei = i
for _ in range(int(math.log10(i)) + 1):
    digit = i % 10
    total += powers[digit]
    i //= 10

Applying those changes to the code make it about twice as fast. Here is what I end up with for the function:

import math

def digit_powers(exponent):
    if exponent <= 1:
        return "The exponent must be at least 2."

    powers = {}
    answer = 0
    # Get the powers
    for a in range(10):
        powers[a] = a ** exponent

    limit = (exponent + 1) * (9 ** exponent)

    # Search for them
    for i in range(10, limit):
        savei = i
        total = 0

        for _ in range(int(math.log10(i)) + 1):
            digit = i % 10
            total += powers[digit]
            i //= 10

        if (total == savei):
            answer += total

    return answer

StackExchange Code Review Q#47714, answer score: 6