# Project Euler # 29: Distinct powers in Python

Consider all integer combinations of ab 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 then placed in numerical order, with any repeats removed, we get the following sequence 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 ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

from time import time

def distinct_terms(n):
"""Assumes n an integer > 1.
returns the sequence generated of a ** b for a and b in range(n)"""
return (x ** y for x in range(2, n + 1) for y in range(2, n + 1))

if __name__ == '__main__':
time1 = time()
print((len(set(distinct_terms(100)))))
print(f'Time: {time() - time1}')


## 1 Answer

Your docstring is misleading.

• The function does not return a sequence; it returns a generator.
• It states “for a and b in range(n)”, which is incorrect. They are in range(2, n+1). If you don’t want to confuse the issue with range() excluding the last value, say “for a and b in the range from 2 to n, inclusive”.
• The problem refers to a “sequence”, where the values are in ascending order and duplicates have been removed, which is completely different from the sequence of values produced by the generator, which is not sorted and can have duplicates.

time1 is a terrible variable name; there is no time2. Perhaps use start_time.

print((len(...))) has an unnecessary extra pair of parenthesis.

Is distinct_terms(n) too specific of a function? Perhaps distinct_terms(m, n) could be more general, where you can generate terms for m <= a,b <= n, instead of always the lower limit of m=2. Or with separate limits for the a and b values.

Python is an easy language to solve this problem in, because $$\100^{100}\$$ is just another integer in Python, despite having 201 digits. If you were to solve this in another programming language, one where integers were restricted to (say) 128 bits, what would you do?

With 99 different values for a and b, you have $$\99^2 = 9801\$$ different $$\a^b\$$ expressions. How many of those will be equivalent? Ie, $$\a^b = c^d\$$? For example, $$\2^4 = 2^{2*2} = {(2^2)}^2 = 4^2\$$. Can you generalize that? Can you count the number of occurrences where that happens, and subtract that from 9801?