p029.py

# Steve Beal
# Project Euler problem 29 solution
# 1/12/15

# Consider all integer combinations of a^b for 2 <= a < =5 and 2 <= b <= 5:
# 2^2 = 4, 2^3 = 8, 2^4 = 16, 2^5 = 32
# 3^2 = 9, 3^3 = 27, 3^4 = 81, 3^5 = 243
# 4^2 = 16, 4^3 = 64, 4^4 = 256, 4^5 = 1024
# 5^2 = 25, 5^3 = 125, 5^4 = 625, 5^5 = 3125

# If they are placed in numerical order, with any repeats removed, we get
# the following sequences of 15 distinct terms:
# 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

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

def distinct_powers(lb1, ub1, lb2=0, ub2=0):
    if lb2 == 0 and ub2 == 0:
        lb2, ub2 = lb1, ub1

    distinct = set()
    for a in range(lb1, ub1+1):
        for b in range(lb2, ub2+1):
            distinct.add(a**b)
    return len(distinct)

print(distinct_powers(2, 100))