🔒 Problem

Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 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 a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

🔐 Key Idea

🔑 Solution

🧭 Initial idea

$O(n)$ complexity.

Since the problem requires us to count the distinct terms, we don't have to calculate the actual integer combinations. Using the fact that $4^4$ is equal to $2^8$, we can easily count all the distinct terms.

🔎 Only counting distinct terms

Starting with $2$, we see that $2^1$, $2^2$, $2^3$, $2^4$, $2^5$, $2^6$ can all be $a$ from $a^b$. Since $2 ≤ b ≤ 100$, all possible outcomes when $a = 2$ would be the following.

$ outcomes = \{ (2^1)^{2...100}, (2^2)^{2...100}, (2^3)^{2...100}, ... (2^6)^{2...100} \} $

Which can be expanded to the following:

$ outcomes = \{ 2^2, 2^3, 2^4, ... 2^{100}, 2^{102}, 2^{104}, ... 2^{588}, 2^{594}, 2^{600} \} $

From this approach, we can derive an algorithm utilitizing Python's set() data structure. Since sets in Python only keep unique values, we can keep all possible unique exponents by just adding values to the set.

🔬 Skipping duplicates

In the example above, we used $2$ for the base, but other values can also be the base. In order to find duplicates, we can use the following algorithm.

Let $n$ and $k$ where $n^k = a$. If $n^k$ is equal to any value that can also be $a$, that $n^k$ is a duplicate.

Therefore, finding all possible pairs of $n$ and $k$ that satisfy $2 ≤ n^k ≤ 100$ would be the same as all possible duplicates.

📜 Actual list of duplicates

We could also derive an algorithm for this process too, but I just found it easier to calculate each one of them. The following is the all possible $n^k$.

When $n = 2$, the set of outcomes would be $ \{ 2^1, 2^2, 2^3, 2^4, 2^5, 2^6 \} $.
When $n = 3$, the set of outcomes would be $ \{ 3^1, 3^2, 3^3, 3^4 \} $.
When $n = 4$, all possible combinations are already covered with case $n = 2$.
When $n = 5$, the set of outcomes would be $ \{ 5^1, 5^2 \} $.
When $n = 6$, the set of outcomes would be $ \{ 6^1, 6^2 \} $.
When $n = 7$, the set of outcomes would be $ \{ 7^1, 7^2 \} $.
When $n = 8$, all possible combinations are already covered with case $n = 2$.
When $n = 9$, all possible combinations are already covered with case $n = 3$.
When $n = 10$, the set of outcomes would be $ \{ 10^1, 10^2 \} $.
When $n ≥ 11$, the set of outcomes would be $ \{ n^1 \} $.

We can categorize all possible $n$ like the following.

2 or more outcomes ($ 2, 3, 5, 6, 7, 10 $ – 6 cases)
- Number of distinct $a^b$ can be directly calculated using the method explained above.
Set of outcomes is already covered somewhere else ($ 2^2, 2^3, 2^4, 2^5, 2^6, 3^2, 3^3, 3^4, 5^2, 6^2, 7^2, 10^2 $ – 12 cases)
- These can be skipped because they will be calculated with the cases above.
Only 1 outcome (all other numbers – 81 cases)
- These will have 99 distinct values because $2 ≤ b ≤ 100$.

max = 100 # upper limit of b (2 ≤ b ≤ 100)

# returns the set of all possible exponents
# equivalent to all unique exponents of {(n^1)^2..max, (n^2)^2..max, ... (n^max_exp)^2..max}
def outcomes(max_exp):
    # uses Python set for unique elements
    s = set()

    # loop for n^1, n^2, ... n^max_exp
    for k in range(1, max_exp + 1):
        # loop for 1*[2..max], 2*[2..max], max_exp*[2..max]
        s.update(list([n*k for n in range(2, max + 1)])) # add exponents to the set
    return s

#            for base of 2      for base of 3      for base of 5, 6, 7, 10
duplicates = len(outcomes(6)) + len(outcomes(4)) + len(outcomes(2)) * 4

# 81 other cases * 99 exponents + edge cases
print(81 * 99 + duplicates)

9183

🔨 Bruteforce method

$O(n^2)$ complexity.

Brute force calculate all possible $a^b$ and store into a set() object to remove duplicates.

result = set()

for i in range(2, 100 + 1):
    result.update([i**j for j in range(2, 100 + 1)])

print(len(result))

9183