Problem 29 : Distinct Powers

Distinct powers

Problem 29

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

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 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?

                                                                                                       (https://projecteuler.net/problem=29)
You know what. If you struggled with this problem, here is a cheat that you can follow.

It's not actual cheating, but there is no complicated algorithms used in this problem like my other solutions in this blog. I'll tell you one thing, and you're all-set.

In Java, there is a type of list called HashSet which only stores distinct values.

For example, I will add 1, 2, 2, 2, 4, 7, and 7 into an ArrayList.

index	0	1	2	3	4	5	6
data	1	2	2	2	4	7	7

Now, I will add 1, 2, 2, 2, 4, 7, and 7 into an HashSet.

index	?	?	?	?
data	1	2	4	7

We cannot directly know in what order the HashSet stores its data, yet we find that all the duplicate values were automatically eliminated, or not stored from the beginning.

And this is why it fulfills our goal: how many distinct terms are in the sequence.

Set<BigInteger> list1 = new HashSet<BigInteger>();
  
for (int a = 2; a <= 100; a++)
{
    for (int b = 2; b <= 100; b++)
    {
     list1.add(BigInteger.valueOf(a).pow(b));
    }
}
System.out.println(list1.size());

We will get 38.04139449846139 ms, or 0.038 seconds. Decent efficiency.

And I will tell you now that I lied. There is actually one more cheat that we can use here.

When we reach some numbers extremely large like a^b where 2 ≤ a, b ≤ 100, they are large enough that each number becomes extremely unique numbers.

So do we need precision? Does it matter that 123456789 is different from 123456788?

... Not really. It's just large number that is about 1.23 x 10⁸. That's all we need.

Therefore, I will simply use double instead of BigInteger.

I guarantee that double will provide enough precision for our calculation for this problem.

Set<Double> list = new HashSet<Double>();
  
for (int a = 2; a <= 100; a++)
{
    for (int b = 2; b <= 100; b++)
    {

        list.add(Math.pow(a, b));
    }
}
System.out.println(list.size());

Yay! 8.5 millisecond!

Answer is 9183
Execution time is 8.553895 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem029.java