Consider all integer combinations of \(a^b\) for \(2 \le a \le 5\) and \(2 \le b \le 5\):
\begin{matrix} 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 \end{matrix}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 \le a \le 100\) and \(2 \le b \le 100\)?
This problem can be solved by hand. There are \(99 \times 99 = 9801\) combinations \(a^b\); the task is to discover how many repeats there are. Note first that if \(a_1^{b_1} = a_2^{b_2}\), then \(a_1\) and \(a_2\) are powers of the same number. This means that there are no repeats among all \(a^b\) where \(a\) is not a power of anything but itself. We take this set to start, then work our way upwards through the powers.
There are six squares that are not also higher powers: \(4, 9, 25, 36, 49, 100\). If \((a^2)^b\) is a duplicate of some previously seen value, that value must be \(a^{2b}\). Thus each of these six bases will produce a duplicate when raised to a power \(b \leq 50\), as \(2b \leq 100\). There are \(49\) such values of \(b\) that produce duplicates, so we have \(6 \times 49 = 294\) repeats in this group.
There are two cubes that are not also higher powers: \(8, 27\). If \((a^3)^b\) is a duplicate, the original is either \((a^2)^{3b/2}\) or \(a^{3b}\), so duplicates for this group occur when \(\frac{3b}2\) or \(3b\) is an integer up to \(100\). The first case has \(b \in \{2, 4, 6, \ldots, 64, 66\}\). The second case has \(b \in \{2, 3, 4, \ldots, 33\}\). The overlap of the two cases is \(b \in \{2, 4, 6, \ldots, 30, 32\}\). By the inclusion-exclusion principle, there are \(33 + 32 - 16 = 49\) values of \(b\) that produce duplicates, so we have \(2 \times 49 = 98\) repeats.
There are two fourth powers that are not also higher powers: \(16, 81\). If \((a^4)^b\) is a duplicate, the original is any of \(a^{4b}\), \((a^2)^{2b}\), and \((a^3)^{4b/3}\). Duplicates for this group occur when \(4b\), \(2b\), or \(4b/3\) is an integer up to \(100\). We disregard the first case as it's a subset of the second. The second case has \(b \in \{2, 3, 4, \ldots, 50\}\). The third case has \(b \in \{3, 6, 9, \ldots, 72, 75\}\). The overlap is \(b \in \{3, 6, 9, \ldots, 45, 48\}\). Again by inclusion-exclusion, there are \(49 + 25 - 16 = 58\) values of \(b\) that produce duplicates, so we have \(2 \times 58 = 116\) repeats.
There is one fifth power: \(32\). If \(32^b\) is a duplicate, the original is any of \(2^{5b}\), \(4^{5b/2}\), \(8^{5b/3}\), and \(16^{5b/4}\). Inclusion-exclusion would be too annoying here so I'm just going to take it case by case. The values of \(b\) in the first case are 2, 3, 4, ..., 20. The previously unseen values of \(b\) in the second case are 22, 24, ..., 38, 40. The third case adds 21, 27, 33, 39, 42, 45, 48, 51, 54, 57, 60. The fourth case adds 44, 52, 56, 64, 68, 72, 76, 80. This is a total of \(19 + 10 + 11 + 8 = 48\) values of \(b\), so we have \(48\) repeats.
Finally, \(64\) is the lone sixth power below our cap for \(a\). If \(64^b\) is a duplicate, the original is any of \(2^{6b}\), \(4^{3b}\), \(8^{2b}\), \(16^{3b/2}\), and \(32^{6b/5}\). The first and second cases are subsets of the third, which gives us all values of \(b\) up to 50. The fourth case adds 52, 54, ..., 66. The fifth case adds 55, 65, 70, 75, 80. This is a total of \(49 + 8 + 5 = 62\) values of \(b\), so we have \(62\) repeats.
Therefore, there are a total of \(294 + 98 + 116 + 48 + 62 = 618\) duplicate values among all combinations \(a^b\). Subtracting this from \(9801\) gives us \(9183\) unique values.