# Project Euler

## Distinct powers

### Problem 29

Consider all integer combinations of *a*^{b} 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 *a*^{b} for 2 ≤ *a* ≤ 100 and 2 ≤ *b* ≤ 100?

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

There are 9 that satisfy the above condition (2 to 10) with b’s where . Let’s extend this to , , and so on, up to . Note and therefore not needed.

For cube, there are 3 that satisfy the above condition (2 to 4) with b’s where . For forth power, there are 2 a’s and 24 b’s and so on.

However, this is not all the duplicates. For any that is a cube, fourth, fifth and sixth power of a smaller and the exponents is divisible by some integer less than the power, there are additional ways to create duplicates. For example, when and and or but :

Similar treatment can be done on forth to sixth power but verifying which value of 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 where it is a composite integer power of some 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 and .