Project Euler 29 - Distinct Powers I have just completed problem 29 from the Project Euler website:


  Consider all integer combinations of \$a^b\$ for \$2 \le a \le 5\$ and \$2 \le b \le 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 \le a \le 100\$ and \$2 \le b \le 100\$?


I have written the code for this problem in Java. With my knowledge of Java, I believe it is as efficient as it can be, however, I think it can be improved further.

import java.util.ArrayList;
import java.math.BigInteger;
public class problemTwentyNine {
  public static void main(String [] args) {
    long start = System.nanoTime();
    ArrayList&lt;BigInteger&gt; distinctTerms = new ArrayList&lt;BigInteger&gt;();
    BigInteger temp;
    for(int i = 2; i &lt;= 100; i++) {
      for(int j = 2; j &lt;= 100; j++) {
        temp = BigInteger.valueOf(i).pow(j);
        if(!distinctTerms.contains(temp)) {
          distinctTerms.add(temp);
        }
      }
    }
    System.out.println("Number of distinct terms: " + distinctTerms.size());
    long stop = System.nanoTime();
    System.out.println("Execution time: " + ((stop - start) / 1e+6) + " ms");
  }
}


Output:


  Number of distinct terms: 9183
  
  Execution time: 306.462625 ms


Now although this is already fairly quick, after looking through some solutions in other languages, I have found that this problem can be solved in just 6 ms in C#. Now I know that it will not be possible in Java as we don't have built in methods like SortedSet.

SortedSet set = new SortedSet();
for (int a = 2; a &lt;= 100; a++) {
    for (int b = 2; b &lt;= 100; b++) {
        double result = Math.Pow(a, b);
        set.Add(result);
     }
 }


C# coded sourced form here.

I'd appreciate any suggestions for ways in which I can improve the performance of the Java solution.
The code is very suboptimal. Keep in mind that Project Euler problems are not about brute force.

You only need to count the distinct powers. You don't have to actually calculate them. Instead, you need to realize that


a base \$a\$ may generate a repeat only if it is a perfect power itself.
each base which is not a perfect power contributes the same amount of unique elements (that is, there is 98 powers of 2, 98 powers of 6, etc) and all such sets are fully disjoint.
sets of elements generated by \$a\$, \$a^2\$, ... \$a^{100}\$ and \$b\$, \$b^2\$, ... \$b^{100}\$ are also equipotent and disjoint.


So, to obtain a solution you need to find out


how many numbers below \$b\$ are not perfect powers (linear complexity),
how many elements are in each set (also linear complexity; think of unique numbers in a multiplication table)


and multiply the results.