# Project Euler

## Distinct powers

### Problem 29

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

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=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?

Using brute force, this problem can be solve by counting all combination of $a^b$ and then sort them to subtract any repeats from the total. This will give a complexity of $O(n^2)$, which for modern computer can be calculate rather quickly for n=100. The total number of terms before removing duplicate can be calculate as $(n-1)^2$. From the example, the one duplicate being removed, $2^4 = 4^2$, has a property that $a_j^2 = a_i$. We can express this as follow:

$(a^2)^b = (a^2)^{b \cdot 1} = (a^2)^{b \cdot \frac{1}{2} \cdot \frac{2}{1}} = (a^{\frac{2}{2}})^{2 \cdot b} = (a)^{2 \cdot b}$

There are 9 $a_i$ that satisfy the above condition (2 to 10) with $99/2 = 49$ b’s where $2 \cdot b_i <= 100$. Let’s extend this to $a_j^3 = a_i$, $a_j^4 = a_i$, and so on, up to $a_j^6 = a_i$. Note $2^7 > 100$ and therefore not needed.

$(a^3)^b = (a^3)^{b \cdot 1} = (a^3)^{b \cdot \frac{1}{3} \cdot \frac{3}{1}} = (a^{\frac{3}{3}})^{3 \cdot b} = (a)^{3 \cdot b}$
$(a^4)^b = (a^4)^{b \cdot 1} = (a^4)^{b \cdot \frac{1}{4} \cdot \frac{4}{1}} = (a^{\frac{4}{4}})^{4 \cdot b} = (a)^{4 \cdot b}$
$\cdots \cdots$

For cube, there are 3 $a_i$ that satisfy the above condition (2 to 4) with $99/3 = 33$ b’s where $3\cdot b_i <= 100$. For forth power, there are 2 a’s and 24 b’s and so on.

However, this is not all the duplicates. For any $a_i$ that is a cube, fourth, fifth and sixth power of a smaller $a_j$ and the exponents $b$ is divisible by some integer less than the power, there are additional ways to create duplicates. For example, when $a_i = a_j^3$ and $2 | b_i$ and $\frac{3b_i}{2} <= 100$ or $b_i \leq 66$ but $b_i > 33$:

$(a^3)^b = (a^3)^{b \cdot 1} = (a^3)^{b \cdot \frac{2}{3} \cdot \frac{3}{2}} = (a^{3 \cdot \frac{2}{3}})^{\frac{3}{2} \cdot b} = (a^2)^{\frac{3}{2} \cdot b}$


Similar treatment can be done on forth to sixth power but verifying which value of $b$ needs to be included at different fraction of the reduced power will be the key to not over or under count. This is especially important for $a_i = 16, 64, 81$ where it is a composite integer power of some $a_j$ and also when the numerator and denominator of the exponent fraction has a greatest common divider that is greater than 1.  The advantage is that it runs extremely fast even with large value of $a$ and $b$.