Project Euler/60

Problem Statement

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.

Link: https://projecteuler.net/problem=60

Solution Approach

Looking for five prime numbers that can satisfy the following constraints:

1. When we take any two primes from the set and concatenate them (either order), result is a prime number
2. Sum of five primes should be smallest possible (there shouldn't be another set of 5 primes with the same properties that are smaller)

Programmatically, here are some constraints we can implement:

1. Start small: minimizing the sum, so smaller primes are better
2. Digit constraints: first digit of any prime (except 2) must be odd, last digit must be 1, 3, 7, 9, so can check those properties are preserved (or quickly rule out candidates) when concatenating primes
3. Use known starting point: the problem gives a known solution for 4 integers, so start by checking for a single 5th prime that meets the constraints.
4. Test each guess: run a check of each prime concatenated, to ensure it is prime. 5 C 2 x 2 = 20 concatenations for each set of 5 primes.

Implementing a solution:

• Implement a way to check 5 primes, 20 different concatenations
• Implement a prime check
• Limit upward complexity (search space): start with smaller primes, set the ceiling low, move it up as we keep running/re-running program
• Use two-pronged solution approach:
  • First, search for extension of known solution (more limited search space)
  • Second, search for new solution (larger search space)

Two main limit values:

• Maximum value of fifth prime to search for (extension case, start with 4-prime base case and find a fifth prime)
• Maximum value of prime numbers to use when looking for 5 new primes (new case, looking for 5 all-new primes meeting the given properties)

Code

See https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem060.java