Project Euler 29 - Distinct Powers

Question

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<BigInteger> distinctTerms = new ArrayList<BigInteger>();
 BigInteger temp;
 for(int i = 2; i <= 100; i++) {
 for(int j = 2; j <= 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 <= 100; a++) {
 for (int b = 2; b <= 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.

• twohundredping: The basic principle you should use here comes from the fundamental theorem of arithmetic. Another key point is that even for the naive method you do not need to recompute powers from scratch every time. Why not use a variable to store \$a^r\$ and use it to compute \$a^{r+1}?\$

Answer 1

Who said Java doesn't have SortedSet?

Although SortedSet is actually a bad option, using a HashSet is much better.

The reason your current calculation is so slow is that it loops through the entire array 10000 times. ArrayList.contains is a \$O(n)\$ operation. HashSet.contains is \$O(1)\$.

In other comments:

• Your class should be named ProblemTwentyNine - or even ProjectEuler29
• BigInteger temp should be put inside the for loops to reduce the scope of it.
• Stop timer before printing out anything. System.out also takes time.
• It is convention to use four spaces of intendation
• Declare BigInteger bigI = BigInteger.valueOf(i); in the outer loop to avoid recreating it 100 times.

Resulting code:

public class ProjectEuler29 {
 public static void main(String [] args) {
 long start = System.nanoTime();
 Set<BigInteger> distinctTerms = new HashSet<BigInteger>();
 for (int i = 2; i <= 100; i++) {
 BigInteger bigI = BigInteger.valueOf(i);
 for (int j = 2; j <= 100; j++) {
 BigInteger temp = bigI.pow(j);
 distinctTerms.add(temp);
 }
 }
 long stop = System.nanoTime();
 System.out.println("Number of distinct terms: " + distinctTerms.size());
 System.out.println("Execution time: " + ((stop - start) / 1e+6) + " ms");
 }
}

A completely different approach

This problem can be seen as a problem about factorizing numbers. Consider \4ドル^2=16\,ドル why is that the same as \2ドル^4\$ ? Because if you factorize it differently, we know that those two values are exactly the same. So this problem is actually solvable without calculating the actual powers, by factorizing the powers instead of calculating them.

I am unsure whether or not this approach would be any increase in speed, but when in doubt about performance there's only one thing to do, benchmark!

• Boris the Spider: It's probably worth noting that this method of measuring performance is woefully broken...
• Simon Forsberg: @BoristheSpider There's always room for another answer! indeed, measuring with a bunch of iterations would be better, because of the JVM warm-up time.

Answer 2

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.

• James: @vnp Thank you for the reply (and sorry for the late reply), however, I haven't been able to apply your answer successfully, myself and some others (including people with degrees etc in maths) have tried to use your idea to solve the solution on paper, and we have had no luck. We believe there may be a problem with your method; could you please review your method to check for any errors etc. Thank you.

Answer 3

I would suggest to try Java 8. I have tested the following solution:

IntStream.rangeClosed(2, 100).boxed()
 .flatMap((a) -> IntStream.rangeClosed(2, 100).boxed()
 .map((b) -> BigInteger.valueOf(a).pow(b)))
 .collect(Collectors.toSet()).size()

The basic idea is to use a flatMap method followed by a collect using a set for collection.

I get on my machine for the following test:

long start = System.nanoTime();
int times = 1000;
for (int i = 0; i < times; i++) {
 IntStream.rangeClosed(2, 100).boxed()
 .flatMap((a) -> IntStream.rangeClosed(2, 100).boxed()
 .map((b) -> BigInteger.valueOf(a).pow(b)))
 .collect(Collectors.toSet()).size();
}
long stop = System.nanoTime();
System.out.println("Execution time: " + (((stop - start) / 1e+6) / times) + " ms");

the following execution time:

Execution time: 7.99952708 ms

It is still brute force, but using a more functional programming style.

Answer 4

I found that switching from pow to multiply made the code run in half the time on my machine.

 final int N = 100;
 long start = System.nanoTime();
 Set<BigInteger> distinctTerms = new HashSet<>();
 for (int a = 2; a <= N; a++) {
 final BigInteger A = BigInteger.valueOf(a);
 BigInteger product = A;
 for (int b = 2; b <= N; b++) {
 product = product.multiply(A);
 distinctTerms.add(product);
 }
 }
 System.out.println("Number of distinct terms: " + distinctTerms.size());
 long stop = System.nanoTime();
 System.out.println("Execution time: " + ((stop - start) / 1e+6) + " ms");

This is essentially your solution modified to use a HashSet as in @SimonForsberg's answer. And then modified to multiply using the previous result rather than take a fresh pow each time (as suggested in @twohundredping's comment).

I also added a constant for 100, as I find it easier to follow that way (and easier to change).

I made A into a constant mainly because it makes the naming conventions work so that a and A are the same value but two different types.

I used a and b instead of i and j because they were in the original problem statement.

My preference would be to stop the timer before producing any output. But I decided to keep it consistent with how you did it instead.