Problem 029


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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s