Project Euler 29

Question

Here's a link to the problem. Is there any way I could optimize/speed up this code, perhaps make it more Pythonic?

"""How many distinct terms are in the sequence
generated by a^b for 2 <= a <= 100
and 2 <= b <= 100?"""

import math
from timeit import default_timer as timer

def distinctPowers(a_max, b_max):
    products = []
    for a in range(2, a_max + 1):
        for b in range(2, b_max + 1):
            if a ** b not in products:
                products.append(a ** b)
    return len(products)

start = timer()
ans = distinctPowers(100, 100)
elapsed_time = (timer() - start) * 1000 # s --> ms

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

Answer 1

You should check the data structure that you use. You are currently using a list, checking if the power exists, and then doing it again when you append unique entries.

If you use a set then you can skip the check and do an add of the power. This is significantly faster... about 50 times if I calculated correctly. Your function would then look like this:

def distinctPowers(a_max, b_max):
    products = set()
    for a in range(2, a_max + 1):
        for b in range(2, b_max + 1):
            products.add(a ** b)
    return len(products)

Answer 2

You can append all of the items to list without checking for uniqueness and in the end get unique elements by converting the list to the set. With this you can write a one-liner:

def distinctPowers(a_max, b_max):
    return len(set([a**b for a in range(2, a_max + 1) for b in range(2, b_max + 1)]))