This is the 29th Project Euler problem. I've been going crazy trying to spot where I've made a mistake.
My thinking is to first assume that there are no duplicate values, i.e. all 99 values of $a$ produce 99 distinct values each, leading to 9801 values. Then I need to calculate how many duplicate values there are and subtract this.
I believe that the only values of $a$ that will produce duplicate values are those that are a perfect value of another number. For example, if $a = 4$, then any value of $b \leq 50$ will be a duplicate as $4^b = (2^2)^b=2^{2b}$. There are 49 numbers between 2 and 50, so we need to take away 49 from 9801.
If I do this for every perfect power $\leq 100$, I obtain the following:
- When $a=4$ there are 49 duplicate values, when $2 \leq b \leq 50$
- When $a=8$ there are 32 duplicate values, when $2 \leq b \leq 33$
- When $a=16$ there are 49 duplicate values, when $2 \leq b \leq 50$ (this one I had to be careful with, as it'd be easy to forget that 16 is not only $2^4$ but also $4^2$)
- When $a=32$ there are 19 duplicate values, when $2 \leq b \leq 20$
- When $a=64$ there are 49 duplicate values, when $2 \leq b \leq 50$
- When $a=9$ there are 49 duplicate values, when $2 \leq b \leq 50$
- When $a=27$ there are 32 duplicate values, when $2 \leq b \leq 33$
- When $a=81$ there are 49 duplicate values, when $2 \leq b \leq 50$
- When $a=25$ there are 49 duplicate values, when $2 \leq b \leq 50$
- When $a=36$ there are 49 duplicate values, when $2 \leq b \leq 50$
- When $a=49$ there are 49 duplicate values, when $2 \leq b \leq 50$
- When $a=100$ there are 49 duplicate values, when $2 \leq b \leq 50$
In general, I believe that to find the number of duplicate values of $a$ when it's a perfect power, I need to find the highest "base" (the largest number that $a$ is a perfect power of) and call this $n$. Then all values of $b$ up to and including $\frac{100}{log_n(a)}$ will produce duplicate values.
However, if I use the above results to calculate $9801 - (49+32+49+19+49+49+32+49+49+49+49+49)$ I get 9277 - an answer that the website is telling me is wrong.
Where is the flaw in my thinking?