Algorithm writing tips?

The first four primes for which any two primes concatenate to produce another prime is 3, 7, 109, 673. For example, if you concatenate 7 and 109, you'll get the prime 7109, and concatenating 109 and 7 yields the prime 1097. The sum of these four primes is 792, and is the lowest sum for the set of four primes with this property.

Find a set of five primes for which any two primes concatenate to produce another prime, and has the lowest sum of such sets of five primes.

--You may use any programming language.
--The script must be written in a fashion that there are no other assumptions made about the nature of the problem without reasonable proof. For example, you may not assume that the highest prime number is below 1,000,000.
--The script execution time preferably produces the answer in under 1 minute for modestly powered computers.
--You may use Google or any other resource to help you. (so long as you don't cheat and look up the answer!)

This is a math problem meant for programming practice. The main problem I'm having is getting the execution time to below 1 minute, but I'm not sure how I can make my algorithm more efficient. Heck, it actually stops when it finds the first set of 5 primes, and it doesn't really check whether it has the lowest sum of all sets of 5 primes. About the only thing I can think of right now is avoiding redundant checks when trying to find larger sets of primes. If anyone has any crazy tips that I don't know about, please feel free to share =)

 Java algorithm

Code:

import java.util.*;

public class Project60 {

    //Find a set of five primes for which any two primes concatenate to produce another
    //prime.
    
    //Hashtable of primes contains keys whose values are determined to be prime.
    private static Hashtable<Long, Boolean> primesTable = new Hashtable<Long, Boolean>();

    //List of primes, whose values are in order.
    private static ArrayList<Long> primesList = new ArrayList<Long>();

    //List of two primes that concatenate to produce primes.
    private static ArrayList<long[]> primesListTwo = new ArrayList<long[]>();

    //List of three primes that concatenate to produce primes.
    private static ArrayList<long[]> primesListThree = new ArrayList<long[]>();

    //List of four primes that concatenate to produce primes.
    private static ArrayList<long[]> primesListFour = new ArrayList<long[]>();
    

    //Algorithm starts by determining the new prime number to compare to existing known sets
    //of primes, if determined.  Each set of primes is checked for compatibility every
    //cycle.  It should be noted that the prime numbers 2 and 5 are excluded since
    //they will NEVER form prime numbers if concatenated last.
    public static void main(String[] args){

        primesList.add(3L);
        long nextPrime = 5;    //the new prime number that gets compared with every cycle
        boolean isCompatible = true;
        double time = System.currentTimeMillis();

        while(true){
            nextPrime += 2;
            while(!isPrime(nextPrime)) nextPrime += 2;
            primesList.add(nextPrime);
            System.out.println(nextPrime);

            //find the next quintuplet(s) of compatible primes.
            for(int i = 0; i < primesListFour.size(); i++){
                long[] list = primesListFour.get(i);
                for(int j = 0; j < list.length && isCompatible; j++){
                    String num1 = "" + list[j] + nextPrime;
                    String num2 = "" + nextPrime + list[j];
                    long n1 = Long.parseLong(num1);
                    long n2 = Long.parseLong(num2);
                    if((primesTable.contains(n1) || isPrime(n1)) &&
                    (primesTable.contains(n2) || isPrime(n2))){
                        primesTable.put(n1, true);
                        primesTable.put(n2, true);
                    }
                    else isCompatible = false;
                }
                if(isCompatible){
                    time = System.currentTimeMillis() - time;
                    time /= 60000;
                    System.out.println("Time: " + time + " minutes.");
                    int sum = 0;
                    for(int j = 0; j < 4; j++){
                        sum += list[j];
                        System.out.println(list[j]);
                    }
                    sum += nextPrime;
                    System.out.println(nextPrime);
                    System.out.println(sum);
                    return;    //end of script
                }
                isCompatible = true;
            }

            //find the next quadruplet(s) of compatible primes.
            for(int i = 0; i < primesListThree.size(); i++){
                long[] list3 = primesListThree.get(i);
                for(int j = 0; j < list3.length && isCompatible; j++){
                    String num1 = "" + list3[j] + nextPrime;
                    String num2 = "" + nextPrime + list3[j];
                    long n1 = Long.parseLong(num1);
                    long n2 = Long.parseLong(num2);
                    if((primesTable.contains(n1) || isPrime(n1)) &&
                    (primesTable.contains(n2) || isPrime(n2))){
                        primesTable.put(n1, true);
                        primesTable.put(n2, true);
                    }
                    else isCompatible = false;
                }
                if(isCompatible){
                    long[] list4 = new long[4];
                    System.arraycopy(list3, 0, list4, 0, 3);
                    list4[3] = nextPrime;
                    primesListFour.add(list4);
                }
                isCompatible = true;
            }

            isCompatible = true;
            //find the next triplet(s) of compatible primes.
            for(int i = 0; i < primesListTwo.size(); i++){
                long[] list2 = primesListTwo.get(i);
                for(int j = 0; j < list2.length && isCompatible; j++){
                    String num1 = "" + list2[j] + nextPrime;
                    String num2 = "" + nextPrime + list2[j];
                    long n1 = Long.parseLong(num1);
                    long n2 = Long.parseLong(num2);
                    if((primesTable.contains(n1) || isPrime(n1)) &&
                    (primesTable.contains(n2) || isPrime(n2))){
                        primesTable.put(n1, true);
                        primesTable.put(n2, true);
                    }
                    else isCompatible = false;
                }
                if(isCompatible){
                    long[] list3 = new long[3];
                    System.arraycopy(list2, 0, list3, 0, 2);
                    list3[2] = nextPrime;
                    primesListThree.add(list3);
                }
                isCompatible = true;
            }

            //find the next pair(s) of compatible primes.
            for(int i = 0; i < primesList.size() - 1; i++){
                String num1 = "" + primesList.get(i) + nextPrime;
                String num2 = "" + nextPrime + primesList.get(i);
                long n1 = Long.parseLong(num1);
                long n2 = Long.parseLong(num2);
                if((primesTable.contains(n1) || isPrime(n1)) &&
                (primesTable.contains(n2) || isPrime(n2))){
                    primesTable.put(n1, true);
                    primesTable.put(n2, true);
                    long[] list = {primesList.get(i), nextPrime};
                    primesListTwo.add(list);
                }
            }
        }// end while(true) loop
    }//end main
    


    //isPrime method utilizes Eratosthenes' Sieve in order to determine prime numbers.
    private static boolean isPrime(long n){
        if(n < 2) return false;
        for(int i = 2; i <= Math.sqrt(n); i++){
            if(n % i == 0) return false;
        }
        return true;
    }
    
}//end class

Btw, I know what the answer is, and it's not as simple as the example made it look. The second number, in ascending order, is 5197 o.O

Can you provide pseudocode of your main section? It's kinda opaque to me & I'm really not sure how long it would take.


Initial thought... I would create a "Prime" class.
fields - value & an array of bits corresponding to the other primes, 0 if they don't produce primes 1 if they do
eg. 3 -> 1*(3), 1(7), 1(11), 0(13), 1(17), ...
7 -> 1(3), 1*(7), 0(11), 0(13), 0(17), ...
11 -> 1(3), 0(7), 1*(11), 0(13), 0(17), ...
* - for calculation reasons, make it 1 with itself
Then to find out which ones work together, AND the arrays of bits.

Code:

private static ArrayLists primeList (single numbers only), other lists of sets of primes.

public static void main(String[] args){
    --Initialize the long nextPrime, to keep track of the new prime being checked every pass of the while(true) loop.
    --Initialize any other stuff as necessary.

    while(true){
        --Find the next prime number in the sequence primeList.  This is the new value of nextPrime.

        --Use nextPrime and concatenate with existing sets of primes (sets of four primes, three, then two) to see if they make larger sets of primes.
        --If a set of five primes is found, print out the results and return;
        --If ANY of the primes fail to concatenate with nextPrime to make a new prime number, the test fails, and the computer moves to the next set of primes.
        --If the set of primes passes the test, a new array for the larger set of primes is added to the corresponding ArrayList.  The old set of primes stays put.

        --Compare existing known primes with nextPrime to see if they make sets of two primes.  This is pretty much the only reason why primeList exists.
    }//end while(true) loop
}

Stereo, why would you set numbers concatenated with themselves as true? They aren't primes for the very obvious reason that they have a factor that is the parent prime. Other than that, I might take a look into your idea.

Oh yeah, you might have noticed a time variable. On the output, it said "Time: 134.60858333333334 minutes."

the isPrime function is not fully functional (in fact, it's horribly slow), as of right now;
- all primes apart from 2 and 3 can be written as 6k+/-1 (But all numbers written as 6k +/- 1 are not primes!)
- even numbers, apart from 2 can be taken out. Since you're not going to include 2 anyway, we may look at every number in binary-form: Every even number has its last bit as 0. Thus:
if ((n & 1) == 1) return false;
This is way faster than returning the modulo of the number. Thing is, you should just skip even numbers anyway. More handy. Faster.

As a sieve looping-technique for this (pseudo):

Code:

long nextPrime(){
-     sets n to the last number stored in sieve,
    solves the 6k +/- 1 = n equation
    if the equation's 6k + 1, set n equal to n + 4 (which makes n = 6k + 5, or 6k - 1)
    else, check if n + 2 is a prime. If it is, add n into the sieve and return n
    
    loop for n = n, then n + 6{
        if n is a prime, add n into the sieve and return n
        if n + 2 is a prime, add n into the sieve and return n
    }
    //oh. Do I have to tell you, if you pineapple the code up, you'll get a free cookie and a never-ending loop? ^,~ Just as a 'lil notice.
    
}

boolean isPrime(long n){
    // if (n < 2) //Hopefully not needed.
        //return false;
    //if ((n & 1) == 1) //skipp'd. Won't be checked by the nextPrime-function anyway.
        //return false;
    if ((n % 5) == 0)
        return false;
    int square of n = (int) Math.sqrt(n); //Most likely no need to be a long.
    loop for prime in prime-sieve until square of n is lower than prime,
        if ((n % prime) == 0)
            return false;
    return true;
}

Stereo, why would you set numbers concatenated with themselves as true? They aren't primes for the very obvious reason that they have a factor that is the parent prime. Other than that, I might take a look into your idea.

For comparison purposes.

ex 3 & 7 & 109 & 673 -> true for 3, 7, 109 and 673 (since all 4 numbers have a true in each of those 4 primes) -> they are a correct set of 4 primes.

Setting it true for itself just kinda indicates which number the array represents, instead of the normal "can concat with this number".


On further thought it might be worth the size hit to make the array of bits include all odd numbers (or all numbers of the form 6*k +- 1), for easier back conversion to what number an index represents. Not sure how often you'd use that function, though.

Code:

                for(int j = 0; j < list.length && isCompatible; j++){
                    String num1 = "" + list[j] + nextPrime;
                    String num2 = "" + nextPrime + list[j];
                    long n1 = Long.parseLong(num1);
                    long n2 = Long.parseLong(num2);
                    if((primesTable.contains(n1) || isPrime(n1)) &&
                    (primesTable.contains(n2) || isPrime(n2))){
                        primesTable.put(n1, true);
                        primesTable.put(n2, true);
                    }

This is the main thing it should hopefully speed up, you don't need to concat the same number multiple times (say "3" is in 50 different 4-tuples, or even 1000 since you said you're working into the 4 and 5 digit numbers, you'd check it with nextPrime once, instead of for each set)

Code:

get nextPrime
for i in Primes
    compare nextPrime+i, i+nextPrime
    if both prime
        i.cat[nextPrime.index] = true
        nextPrime.cat[i.index] = true
put nextPrime in Primes
nextPrime.cat[nextPrime.index] = true

Code:

check(n-tuple) returns n+1 tuple
for prime j in n-tuple
    if(j.cat[nextPrime.index] && nextPrime.cat[j.index])
        do nothing
    else
        return null
return nextPrime+n-tuple

the isPrime function is not fully functional (in fact, it's horribly slow), as of right now;
- all primes apart from 2 and 3 can be written as 6k+/-1 (But all numbers written as 6k +/- 1 are not primes!)
[COLOR="DarkOrange"]- even numbers, apart from 2 can be taken out. Since you're not going to include 2 anyway, we may look at every number in binary-form: Every even number has its last bit as 0. Thus:
if ((n & 1) == 1) return false;
This is way faster than returning the modulo of the number. Thing is, you should just skip even numbers anyway. More handy. Faster.[/COLOR]

As a sieve looping-technique for this (pseudo):

Code:

long nextPrime(){
-     sets n to the last number stored in sieve,
    solves the 6k +/- 1 = n equation
    if the equation's 6k + 1, set n equal to n + 4 (which makes n = 6k + 5, or 6k - 1)
    else, check if n + 2 is a prime. If it is, add n into the sieve and return n
    
    loop for n = n, then n + 6{
        if n is a prime, add n into the sieve and return n
        if n + 2 is a prime, add n into the sieve and return n
    }
    [color=Magenta]//oh. Do I have to tell you, if you pineapple the code up, you'll get a free cookie and a never-ending loop? ^,~ Just as a 'lil notice.[/color]
    
}

boolean isPrime(long n){
    // if (n < 2) //Hopefully not needed.
        //return false;
    //if ((n & 1) == 1) //skipp'd. Won't be checked by the nextPrime-function anyway.
        //return false;
    if ((n % 5) == 0)
        return false;
    int square of n = (int) Math.sqrt(n); //Most likely no need to be a long.
    loop for prime in prime-sieve until square of n is lower than prime,
        if ((n % prime) == 0)
            return false;
    return true;
}

That's a pattern that's been eluding me all this time xD Your parenthetical statement seems to be in conflict though...

Having seen that, I'm smacking myself in the head for such a stupid oversight. I've come to the conclusion that I should only check for input % n, where n is a prime number. I'm not familiar with the code (n & 1), but I understand what you mean.

Oyas! That's why I use the debugger (whatever works) and check each section of code that I write in a progressive sequence, and I ask the computer for an appropriate output to make sure that my code works before moving on. Personally my worst enemies are recursions methods.

For comparison purposes.

[COLOR="Black"]ex 3 & 7 & 109 & 673 -> true for 3, 7, 109 and 673 (since all 4 numbers have a true in each of those 4 primes) -> they are a correct set of 4 primes.

Setting it true for itself just kinda indicates which number the array represents, instead of the normal "can concat with this number".


On further thought it might be worth the size hit to make the array of bits include all odd numbers (or all numbers of the form 6*k +- 1), for easier back conversion to what number an index represents. Not sure how often you'd use that function, though.

[COLOR="Blue"]

Code:

                for(int j = 0; j < list.length && isCompatible; j++){
                    String num1 = "" + list[j] + nextPrime;
                    String num2 = "" + nextPrime + list[j];
                    long n1 = Long.parseLong(num1);
                    long n2 = Long.parseLong(num2);
                    if((primesTable.contains(n1) || isPrime(n1)) &&
                    (primesTable.contains(n2) || isPrime(n2))){
                        primesTable.put(n1, true);
                        primesTable.put(n2, true);
                    }

This is the main thing it should hopefully speed up, you don't need to concat the same number multiple times (say "3" is in 50 different 4-tuples, or even 1000 since you said you're working into the 4 and 5 digit numbers, you'd check it with nextPrime once, instead of for each set)[/COLOR]

Code:

get nextPrime
for i in Primes
    compare nextPrime+i, i+nextPrime
    if both prime
        i.cat[nextPrime.index] = true
        nextPrime.cat[i.index] = true
put nextPrime in Primes
nextPrime.cat[nextPrime.index] = true

Code:

check(n-tuple) returns n+1 tuple
for prime j in n-tuple
    [COLOR="Lime"]if(j.cat[nextPrime.index] && nextPrime.cat[j.index])
        do nothing[/COLOR]
    else
        return null
return nextPrime+n-tuple

[/color]

[COLOR="Black"]Hmm, still seems sketchy to me. Especially if you're thinking about using that boolean as an "array representative" since after the calculations are done and over with, there's no way to know whether it was n.cat(n) unless you say if(i == j) in some double looping of indexes, in which case there really isn't much of a point in setting a boolean. Or am I missing something else?

Just to make it clear though, I'm okay without having to think about the "array representative".[/COLOR]

This was one of the original concerns I addressed in the OP, and I haven't really thought up of a reliable way how to prevent duplicate calculations according to my current algorithm. Especially considering that by the time nextPrime reaches ~2500, there are well over 4000 sets of two primes!

Is this allowed in conventional code writing? Silly question, but I've always wondered xD (my guess is yes)

That's a pattern that's been eluding me all this time xD Your parenthetical statement seems to be in conflict though...

Having seen that, I'm smacking myself in the head for such a stupid oversight. I've come to the conclusion that I should only check for input % n, where n is a prime number. I'm not familiar with the code (n & 1), but I understand what you mean.

Oyas! That's why I use the debugger (whatever works) and check each section of code that I write in a progressive sequence, and I ask the computer for an appropriate output to make sure that my code works before moving on. Personally my worst enemies are recursions methods.

One genius thing you did here. Colourizing. Too bad I'm not going to bother to do the same, sorry

Sorry, I've been using lisp too much, that may be why there are too many parentheses.

I've been somewhat unfamiliar with how Java works, but I'm quite sure it can be written as (n & 1 == 1).
With that being said, I'll try to explain it quite short. For a human being, to calculate this, we would have to convert n and 1 into bitcode. Let's say n equals 23:

Base 10	Base 2
1	00001
23	10111

Now, let's see how & reacts

	00001
&	10111
=	00001

Though it may look completely in-understandable, it's the bitwise &-operator. If two bits at same position equals 1, then the bit at that position is set as 1. Else, it is set as 0. Another example:

	1011010101110001001
&	0010111101010111010
=	0010010101010001000

It can be proven that any given number n is a number divisible by 2 if (n & 1 == 0).
Compared to base 10, it's like saying that any number n is divisible by 10 if the last digit in the number is 0.

Is this allowed in conventional code writing? Silly question, but I've always wondered xD (my guess is yes)

Really you would probably do if(!(s1 && s2)), or if(!s1 || !s2) but I did it that way

One genius thing you did here. Colourizing. Too bad I'm not going to bother to do the same, sorry

Sorry, I've been using lisp too much, that may be why there are too many parentheses.

I've been somewhat unfamiliar with how Java works, but I'm quite sure it can be written as (n & 1 == 1).
With that being said, I'll try to explain it quite short. For a human being, to calculate this, we would have to convert n and 1 into bitcode. Let's say n equals 23:

Base 10	Base 2
1	00001
23	10111

Now, let's see how & reacts

	00001
&	10111
=	00001

Though it may look completely in-understandable, it's the bitwise &-operator. If ...

oic. That's why I didn't understand the code itself. Java doesn't recognize integers or bytes as bit-wise for anything except XOR or char types, and is one of the gh3y things about Java. Strong type ftl. . Also, shouldn't there be a notation denoting that the 1 is a base-2 number? Such as hex number 0xAF.

oic. That's why I didn't understand the code itself. Java doesn't recognize integers or bytes as bit-wise for anything except XOR or char types, and is one of the gh3y things about Java. Strong type ftl. . Also, shouldn't there be a notation denoting that the 1 is a base-2 number? Such as hex number 0xAF.

Really?

Code:

public class Test{
    public static void main(String args[]){
        for (long i = 0; i < 11; i++)
            System.out.println(i & 1);
    }
}

Should deliver a repeating 0-1-0-1-0... pattern. I just tested it.

There's no base-2 number in Java. It doesn't really matter, as all numbers in whatever base (as long as it is integer-based bases) will have 1 as 1 in all bases. Besides, even if I converted it to a base-2 number, it wouldn't matter much. Take for example 0xAF:

System.out.println(0xAF);

That returns 175. Now, if you replace all 0xAF to 175, your code will run as nothing happened (As long you haven't used 0xAF in regex or strings, that is.).

Java does support bitwise operators.

As for the statement (n & 1 == 1), that should work fine in Java (or any other languages too IMO) due to the order of operations, ie & has precedent over ==. This should be in the basic syntax of a programming language. This order of precedent is the same as how multiply gets executed before addition.

Oops, my bad, I forgot the "== 1" part >.<

I decided to run the script again using a new isPrime method (while doing some college work), and the time was roughly the same o.O Hmm...

That's not to say I'm blaming anyone though. It just means that the majority of the time is being spent on comparing sets of primes with nextPrime.

Code:

private static boolean isPrime(long n){
        if(n <= 2) return false;
        if(n % 5 == 0) return false;
        int i = 0;
        int squareRoot = (int) Math.sqrt(n);
        for(i = 0; i < primesList.size() && primesList.get(i) <= squareRoot; i++){
            if(n % primesList.get(i) == 0) return false;
        }
        //this for loop is necessary because sqrt(n) early on is usually larger than the largest prime in primesList.
        if(primesList.get(primesList.size() - 1) <= squareRoot){
            for(long j = primesList.get(primesList.size() - 1) + 2; j <= Math.sqrt(n); j += 2){
                if(n % j == 0) return false;
            }
        }
        return true;
    }

This would be, more or less, the best way to use the Sieve for the purposes of this problem, no?

Oops, my bad, I forgot the "== 1" part >.<

I decided to run the script again using a new isPrime method (while doing some college work), and the time was roughly the same o.O Hmm...

That's not to say I'm blaming anyone though. It just means that the majority of the time is being spent on comparing sets of primes with nextPrime.

Code:

private static boolean isPrime(long n){
        if(n <= 2) return false;
        if(n % 5 == 0) return false;
        int i = 0;
        int squareRoot = (int) Math.sqrt(n);
        for(i = 0; i < primesList.size() && primesList.get(i) <= squareRoot; i++){
            if(n % primesList.get(i) == 0) return false;
        }
        //this for loop is necessary because sqrt(n) early on is usually larger than the largest prime in primesList.
        if(primesList.get(primesList.size() - 1) <= squareRoot){
            for(long j = primesList.get(primesList.size() - 1) + 2; j <= Math.sqrt(n); j += 2){
                if(n % j == 0) return false;
            }
        }
        return true;
    }

This would be, more or less, the best way to use the Sieve for the purposes of this problem, no?

Yeah, that works. When initiating the prime-list, you can loop like this (pseudo):

Code:

loop for x = 5 then x + 6
if (isPrime(x))
add x in sieve
if (isPrime(x+2))
add x+2 in sieve

Add in 3 and remove 5, and you'll be fine. This will, most likely, increase the prime-checking part quite a lot. Whether that increases overall runtime by much or not, depends on the time it takes to run the other parts of the algorithm.

Technically, you can generate a list of prime really fast using the 6k+/-1 rule, like what DS said, or here's another version.

First off, 2, 3, 5, 7 are the basic primes, having 5 and 7 being the first set belongs to the 6k+/-1 rule. After that, just loop:
for(i = 12; i < some_limit; i+=6)
{
if(is_prime(i-1))
// do something
if(is_prime(i+1))
// do the same thing
}

Yeah, that works. When initiating the prime-list, you can loop like this (pseudo):

Code:

loop for x = 5 then x + 6
if (isPrime(x))
add x in sieve
if (isPrime(x+2))
add x+2 in sieve

Add in 3 and remove 5, and you'll be fine. This will, most likely, increase the prime-checking part quite a lot.

I doubt it'll make much of a difference at all.

isPrime checks for multiples of 2 and 3 first (or should) and most of the time running it is spent on numbers that are actually prime.

Generating and adding the primes up to 2000000: 2.8 seconds
Incrementing the counter by 2 instead of 1 (checking 1/2 as many numbers): 2.6 seconds

Hmm. For myself, looping from 1 to 2 million takes 53 seconds with this algorithm without jumping. With looping from 5 to 2 million, incrementing by 6 and checking every x and x+2 number, I get 45 seconds. (With LISP, that is) That's over 10% increase in speed, and I'd consider that as a lot.

How long does it take to make something like this? @___@

 The new algorithm

Code:

import java.util.*;

public class Project60 {

    //Find a set of five primes for which any two primes concatenate to produce another
    //prime.
    
    private static Hashtable<Long, Boolean> primesRecall = new Hashtable<Long, Boolean>();
    private static ArrayList<Long> primesList = new ArrayList<Long>();
    
    public static void main(String[] args){
        double time = System.currentTimeMillis();
        primesList.add(3L);
        primesList.add(7L);
        long nxtPrime = 11L;
        int digitLimit = 4;
        
        while(true){
            
            //Fills the primesList ArrayList.
            while(nxtPrime <= Math.pow(10, digitLimit)){
                if(isPrime(nxtPrime)){
                    primesList.add(nxtPrime);
                    primesRecall.put(nxtPrime, true);
                }
                nxtPrime += 2;
                if(isPrime(nxtPrime)){
                    primesList.add(nxtPrime);
                    primesRecall.put(nxtPrime, true);
                }
                nxtPrime += 4;
            }
            while(true){
                if(isPrime(nxtPrime)){
                    primesList.add(nxtPrime);
                    primesRecall.put(nxtPrime, true);
                    break;
                }
                nxtPrime += 2;
                if(isPrime(nxtPrime)){
                    primesList.add(nxtPrime);
                    primesRecall.put(nxtPrime, true);
                    break;
                }
                nxtPrime += 4;
            }
            
            time = System.currentTimeMillis() - time;
            time /= 60000;
            System.out.println("Step 1 Time: " + time + " minutes.");
            time = System.currentTimeMillis();
            
            //Fill a complete primesTable of what primes concatenate with other primes
            //to produce new primes, in preparation for the next step.
            int size = primesList.size();
            boolean[][] primesTable = new boolean[size][size];
            long prime1 = 0;
            for(int i = 0; i < size - 1; i++){
                prime1 = primesList.get(i);
                long prime2 = 0;
                for(int j = 0; j < size - 1; j++){
                    prime2 = primesList.get(j);
                    long result1 = 0;
                    long result2 = 0;
                    for(int k = 1; result1*result2 == 0; k++){
                        long power = (long)Math.pow(10, k);
                        if(power > prime2 && result1 == 0)
                            result1 = prime1 * power + prime2;
                        if(power > prime1 && result2 == 0)
                            result2 = prime2 * power + prime1;
                    }
                    if((isPrime(result1)) &&
                            (isPrime(result2))){
                        primesTable[i][j] = true;
                        primesTable[j][i] = true;
                    }
                }
            }
            
            time = System.currentTimeMillis() - time;
            time /= 60000;
            System.out.println("Step 2 Time: " + time + " minutes.");
            time = System.currentTimeMillis();
            
            //Attempt to find the set of five primes, if it exists.
            for(int i1 = 0; i1 < size; i1++){
                for(int i2 = 0; i2 < size; i2++){
                    for(int i3 = 0; i3 < size &&
                            primesTable[i1][i2]; i3++){
                        for(int i4 = 0; i4 < size &&
                                primesTable[i1][i3] &&
                                primesTable[i2][i3]; i4++){
                            for(int i5 = 0; i5 < size &&
                                    primesTable[i1][i4] &&
                                    primesTable[i2][i4] &&
                                    primesTable[i3][i4]; i5++){
                                if(primesTable[i1][i5] &&
                                        primesTable[i2][i5] &&
                                        primesTable[i3][i5] &&
                                        primesTable[i4][i5]){
                                    System.out.println(primesList.get(i1));
                                    System.out.println(primesList.get(i2));
                                    System.out.println(primesList.get(i3));
                                    System.out.println(primesList.get(i4));
                                    System.out.println(primesList.get(i5));
                                    System.out.println("Sum: " + (primesList.get(i1) +
                                            primesList.get(i2) + primesList.get(i3) +
                                            primesList.get(i4) + primesList.get(i5)));
                                
                                    time = System.currentTimeMillis() - time;
                                    time /= 60000;
                                    System.out.println("Step 3 Time: " + time + " minutes.");
                                    time = System.currentTimeMillis();
                                
                                    return;
                                }
                            }
                        }
                    }
                }
            }
            
            time = System.currentTimeMillis() - time;
            time /= 60000;
            System.out.println("Step 3 Time: " + time + " minutes.");
            time = System.currentTimeMillis();

            //Set of 5 primes is not found.  Increase search area.
            System.out.println("Increasing search area...");
            digitLimit++;
        }
    }
    
    private static boolean isPrime(long n){
        if(n % 2 == 0 || n % 5 == 0) return false;
        for(int i = 0; primesList.get(i) <= Math.sqrt(n); i++){
            if(n % primesList.get(i) == 0) return false;
        }
        return true;
    }
    
}

Okay, so after using Stereo's suggestion (nothing tricky with duplicate primes >_>), and meticulously testing each step of my new v3.0 algorithm, I have the results:

Output:

Code:

Step 1 Time: 2.1666666666666666E-4 minutes.
Step 2 Time: 0.38053333333333333 minutes.
[prime 1]
[prime 2]
[prime 3]
[prime 4]
[prime 5]
Sum: [sum]
Step 3 Time: 7.5E-4 minutes.

That's definitely an execution time of less than a minute =D Fitting a check to ensure that the sum of the 5 primes is the lowest is trivial at this point, aside from the "OutOfMemoryException" caused by the large-ass boolean table.

Thanks a lot Stereo and Devil's Sunrise! I've learned quite a few things from this exercise.

Something I thought about later... sqrt is not cheap (iirc it uses Newton's method to approximate?).

primesList.get(i) <= Math.sqrt(n)
Use
primeslist.get(i)**2 <= n

Something I thought about later... sqrt is not cheap (iirc it uses Newton's method to approximate?).

primesList.get(i) <= Math.sqrt(n)
Use
primeslist.get(i)**2 <= n

Huh... not sure why I didn't think about this earlier. The sqrt method uses an iterative equation, that's for sure. One such method: sqrt(2) = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

The total operation time was reduced about 20%. Not bad.