1
\$\begingroup\$

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}')
\$\endgroup\$
2
\$\begingroup\$

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?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.