import org.apache.commons.math3.util.Combinations;

import java.io.IOException;
import java.util.Arrays;

public class P60_PrimePairSets {
    // Project Euler - Problem 60 - Prime pair sets
    // The primes 3, 7, 109, and 673, are quite remarkable.
    // By taking any two primes and concatenating them in any order the result will always be prime.
    // For example, taking 7 and 109, both 7109 and 1097 are prime.
    // The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.
    // Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

    private static final int SET_SIZE = 5;
    private static boolean FORWARD = true;
    private static boolean BACKWARD = !FORWARD;
    private static Prime1stMillion primes;
    private static long[] primeArray;

    public static void main(String[] args) {
        String message = "The lowest sum for a set of five primes " +
                "for which any two primes concatenate to produce another prime is %d.\n";
        long primeSum = P60_PrimePairSets.findPrimeSum(SET_SIZE);
        showSolutionPrimeArray();
        System.out.printf(message, primeSum);
    }

    static {
        try {
            primes = new Prime1stMillion();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    static long findPrimeSum(int arraySize) {
        return getSum(findPrimeArray(arraySize));
    }

    static long[] findPrimeArray(int arraySize) {
        for (int maxPrimeIndex = arraySize; true; maxPrimeIndex++) {
            System.out.printf("Checking for last prime %,d\n", primes.get(maxPrimeIndex));
            primeArray = searchPrimeArray(arraySize, maxPrimeIndex);
            if (primeArray != null) return primeArray;
        }
    }

    static long[] searchPrimeArray(int setSize, int maxPrimeIndex) {
        for (int[] combo : new Combinations(maxPrimeIndex, setSize - 1)) {
            primeArray = getPrimeArray(setSize, maxPrimeIndex, combo);
            if (isConcatenable(setSize, primeArray)) return primeArray;
        }
        return null;
    }

    static long[] getPrimeArray(int arraySize, int maxPrimeIndex, int[] combo) {
        primeArray = new long[arraySize];
        primeArray[arraySize - 1] = primes.get(maxPrimeIndex);
        for (int j = 0; j <= arraySize - 2; j++) primeArray[j] = primes.get(combo[j] + 1);
        return primeArray;
    }

    static boolean isConcatenable(int setSize, long[] primeArray) {
        for (int[] pair : new Combinations(setSize, 2)) {
            if (!isConcatenable(primeArray, pair, FORWARD)) return false;
            if (!isConcatenable(primeArray, pair, BACKWARD)) return false;
        }
        return true;
    }

    static boolean isConcatenable(long[] primeArray, int[] pair, boolean forward) {
        int first = forward ? 0 : 1;
        int second = forward ? 1 : 0;
        return primes.isPrime(concatenate(primeArray[pair[first]], primeArray[pair[second]]));
    }

    static long concatenate(long prime1, long prime2) {
        return Long.parseLong("" + prime1 + prime2);
    }

    static long getSum(long[] primeArray) {
        long sum = 0;
        for (long aPrimeArray : primeArray) sum += aPrimeArray;
        return sum;
    }

    private static void showSolutionPrimeArray() {
        System.out.printf("Solution prime set = %s\n", Arrays.toString(primeArray));
    }
}

@@ -90,22 +90,17 @@
 va.util.
-Arrays
+*
 ;%0A%0Apubli
@@ -666,16 +666,72 @@
 nal int 
+PRIME_ARRAY_SIZE = 5;%0A    private static final int HASH_
 SET_SIZE
@@ -725,33 +725,37 @@
 HASH_SET_SIZE = 
-5
+30000
 ;%0A    private st
@@ -911,16 +911,64 @@
 meArray;
+%0A    private static List%3CSet%3CInteger%3E%3E hashSets;
 %0A%0A    pu
@@ -1221,19 +1221,27 @@
 rimeSum(
-SET
+PRIME_ARRAY
 _SIZE);%0A
@@ -1340,16 +1340,66 @@
 tatic %7B%0A
+        hashSets = new ArrayList%3CSet%3CInteger%3E%3E();%0A
         
@@ -1718,25 +1718,17 @@
 Index = 
-arraySize
+0
 ; true; 
@@ -1833,24 +1833,67 @@
 imeIndex));%0A
+            updateHashSets(maxPrimeIndex);%0A
             
@@ -2017,32 +2017,40 @@
    %7D%0A    %7D%0A%0A    
+private 
 static long%5B%5D se
@@ -2064,27 +2064,29 @@
 meArray(int 
-set
+array
 Size, int ma
@@ -2112,439 +2112,137 @@
     
-for (int%5B%5D combo : new Combinations(maxPrimeIndex, setSize - 1)) %7B%0A            primeArray = getPrimeArray(setSize, maxPrimeIndex, combo);%0A            if (isConcatenable(setSize, primeArray)) return primeArray;%0A        %7D%0A        return null;%0A    %7D%0A%0A    static long%5B%5D getPrimeArray(int arraySize, int maxPrimeIndex, int%5B%5D combo) %7B%0A        primeArray = new long%5BarraySize%5D;%0A        primeArray%5BarraySize - 1%5D = primes.get(maxPrimeIndex
+return new long%5B0%5D;%0A    %7D%0A%0A    private static void updateHashSets(int index) %7B%0A        hashSets.set(index, new HashSet%3CInteger%3E()
 );%0A 
@@ -2261,389 +2261,129 @@
 int 
-j
+i
  = 0; 
-j %3C= arraySize - 2; j
+i %3C index; i
 ++) 
-primeArray%5Bj%5D = primes.get(combo%5Bj%5D + 1);%0A        return primeArray;%0A    %7D%0A%0A    static boolean isConcatenable(int setSize, long%5B%5D primeArray) %7B%0A        for (int%5B%5D pair : new Combinations(setSize, 2)) %7B%0A            if (!isConcatenable(primeArray, pair, FORWARD)) return false;%0A            if (!isConcatenable(primeArray, pair, BACKWARD)) return false
+%7B%0A            if (isConcatenablePair(primes.get(i), primes.get(index))) hashSets.get(i).add(index)
 ;%0A  
@@ -2398,35 +2398,22 @@
     
+%7D%0A%0A
     
-return true;%0A    %7D%0A%0A   
+private
  sta
@@ -2442,142 +2442,112 @@
 able
+Pair
 (long
-%5B%5D primeArray, int%5B%5D pair, boolean forward) %7B%0A        int first = forward ? 0 : 1;%0A        int second = forward ? 1 : 0;%0A
+ left, long right) %7B%0A        return primes.isPrime(concatenate(right, left)) &&%0A       
         
 retu
@@ -2534,38 +2534,32 @@
 %0A               
-return
  primes.isPrime(
@@ -2574,57 +2574,19 @@
 ate(
-primeArray%5Bpair%5Bfirst%5D%5D
+left
 , 
-p
 ri
-meArray%5Bpair%5Bsecond%5D%5D
+ght
 ));%0A

rework algorithm to use array of sets, sets track concatenable prime pairs