Problem 44: Pentagonal numbers are generated by the formula, Pn=n(3*n-1)/2. The first ten pentagonal numbers are:
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 – 22 = 48, is not pentagonal.
Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference is pentagonal and D = |Pk – Pj| is minimised; what is the value of D?
import java.util.Collections;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.Vector;
class runner
{
private static int makepentagonal(int n){
int y = n*(3*n-1)/2;
if(storage.contains(y)) return y;
storage.add(y);
return y;
}
private static boolean accept(int x, int y){
int sum = x+y;
if(storage.size() == 0){
makepentagonal(1);
}
while(sum > storage.last()){
makepentagonal(storage.size()+1);
}
if(!storage.contains(sum)) return false;
if(!storage.contains(x-y)) return false;
return true;
}
static TreeSet storage = new TreeSet();
public static void main (String[] args) throws java.lang.Exception
{
long time = System.currentTimeMillis();
int d = -1;
int x = 1;
outerLoop:
while(true){
int px = makepentagonal(x);
SortedSet headset = storage.headSet(px);
Vector lazy = new Vector();
for(int py : headset){//Get around java.util.ConcurrentModificationException
lazy.add(py);
}
for(int py: lazy){
if(accept(px,py)){
d = px-py;
break outerLoop;
}
}
x++;
}
System.out.println("D:"+d);
System.out.println("time: "+(System.currentTimeMillis() - time));
}
}
Note: Using TreeSet for storage vs Vector sped up the execution time significantly (950ms vs 110seconds)