Solution to 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.
Updated: Aug. 15, 2022 — Training Time: 7 minutes
Overseen by: Archangel Macsika
All Training Resources
Scroll for more menu list
Topic: Project Euler Problem 60: Prime pair sets.
Difficulty: Expert.
Objective: 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.
Input: None.
Expected Output: 26033.
Sikademy Solution in Java Programming Language
package sikademy;
/**
*
* @author Archangel Macsika
* Copyright (c) Sikademy. All rights reserved
*/
import java.util.Arrays;
import java.util.BitSet;
public class SikademyEulerSolution {
private static final int PRIME_LIMIT = 100000; // Arbitrary initial cutoff
private int[] primes = Library.listPrimes(PRIME_LIMIT);
// Memoization
private BitSet isConcatPrimeKnown;
private BitSet isConcatPrime;
public String run() {
isConcatPrimeKnown = new BitSet(primes.length * primes.length);
isConcatPrime = new BitSet(primes.length * primes.length);
int sumLimit = PRIME_LIMIT;
while (true) {
int sum = findSetSum(new int[]{}, 5, sumLimit - 1);
if (sum == -1) // No smaller sum found
return Integer.toString(sumLimit);
sumLimit = sum;
}
}
/*
* Tries to find any suitable set and return its sum, or -1 if none is found.
* A set is suitable if it contains only primes, its size is 'targetSize',
* its sum is less than or equal to 'sumLimit', and each pair concatenates to a prime.
* 'prefix' is an array of ascending indices into the 'primes' array,
* which describes the set found so far.
* The function blindly assumes that each pair of primes in 'prefix' concatenates to a prime.
*
* For example, findSetSum(new int[]{1, 3, 28}, 5, 10000) means "find the sum of any set
* where the set has size 5, consists of primes with the lowest elements being {3, 7, 109},
* has sum 10000 or less, and has each pair concatenating to form a prime".
*/
private int findSetSum(int[] prefix, int targetSize, int sumLimit) {
if (prefix.length == targetSize) {
int sum = 0;
for (int i : prefix)
sum += primes[i];
return sum;
} else {
int i;
if (prefix.length == 0)
i = 0;
else
i = prefix[prefix.length - 1] + 1;
outer:
for (; i < primes.length && primes[i] <= sumLimit; i++) {
for (int j : prefix) {
if (!isConcatPrime(i, j) || !isConcatPrime(j, i))
continue outer;
}
int[] appended = Arrays.copyOf(prefix, prefix.length + 1);
appended[appended.length - 1] = i;
int sum = findSetSum(appended, targetSize, sumLimit - primes[i]);
if (sum != -1)
return sum;
}
return -1;
}
}
// Tests whether parseInt(toString(x) + toString(y)) is prime.
private boolean isConcatPrime(int x, int y) {
int index = x * primes.length + y;
if (isConcatPrimeKnown.get(index))
return isConcatPrime.get(index);
x = primes[x];
y = primes[y];
int mult = 1;
for (int temp = y; temp != 0; temp /= 10)
mult *= 10;
boolean result = isPrime((long)x * mult + y);
isConcatPrimeKnown.set(index);
isConcatPrime.set(index, result);
return result;
}
private boolean isPrime(long x) {
if (x < 0)
throw new IllegalArgumentException();
else if (x == 0 || x == 1)
return false;
else {
long end = sqrt(x);
for (int p : primes) {
if (p > end)
break;
if (x % p == 0)
return false;
}
for (long i = primes[primes.length - 1] + 2; i <= end; i += 2) {
if (x % i == 0)
return false;
}
return true;
}
}
public static boolean[] listPrimality(int n) {
if (n < 0)
throw new IllegalArgumentException("Negative array size");
boolean[] result = new boolean[n + 1];
if (n >= 2)
result[2] = true;
for (int i = 3; i <= n; i += 2)
result[i] = true;
// Sieve of Eratosthenes
for (int i = 3, end = sqrt(n); i <= end; i += 2) {
if (result[i]) {
// Note: i * i does not overflow
for (int j = i * i, inc = i * 2; j <= n; j += inc)
result[j] = false;
}
}
return result;
}
public static int sqrt(int x) {
if (x < 0)
throw new IllegalArgumentException("Square root of negative number");
int y = 0;
for (int i = 1 << 15; i != 0; i >>>= 1) {
y |= i;
if (y > 46340 || y * y > x)
y ^= i;
}
return y;
}
public static int[] listPrimes(int n) {
boolean[] isPrime = listPrimality(n);
int count = 0;
for (boolean b : isPrime) {
if (b)
count++;
}
int[] result = new int[count];
for (int i = 0, j = 0; i < isPrime.length; i++) {
if (isPrime[i]) {
result[j] = i;
j++;
}
}
return result;
}
public static void main(String[] args) {
SikademyEulerSolution solution = new SikademyEulerSolution();
System.out.println(solution.run());
}
}
Sikademy Solution in Python Programming Language
#
# @author Archangel Macsika
# Copyright (c) Sikademy. All rights reserved.
#
import time, random, math
def sieve(n):
is_prime = [True]*n
is_prime[0] = False
is_prime[1] = False
is_prime[2] = True
# even numbers except 2 have been eliminated
for i in range(3, int(n**0.5+1), 2):
index = i*2
while index < n:
is_prime[index] = False
index = index+i
prime = [2]
for i in range(3, n, 2):
if is_prime[i]:
prime.append(i)
return prime
# Miller–Rabin primality test
# One of the best algorithm to check if the given number if prime
# https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
# Algorithm: http://bit.ly/2drtk0x
def is_prime(n, k = 3):
if n < 6: # assuming n >= 0 in all cases... shortcut small cases here
return [False, False, True, True, False, True][n]
elif n % 2 == 0: # should be faster than n % 2
return False
else:
s, d = 0, n - 1
while d % 2 == 0:
s, d = s + 1, d >> 1
# A for loop with a random sample of numbers
for a in random.sample(range(2, n-2), k):
x = pow(a, d, n)
if x != 1 and x + 1 != n:
for r in range(1, s):
x = pow(x, 2, n)
if x == 1:
return False # composite for sure
elif x == n - 1:
a = 0 # so we know loop didn't continue to end
break # could be strong liar, try another a
if a:
return False # composite if we reached end of this loop
return True # probably prime if reached end of outer loop
def comb(a, b):
len_a = math.floor(math.log10(a))+1
len_b = math.floor(math.log10(b))+1
if is_prime(int(a*(10**len_b)+b)) and is_prime(int(b*(10**len_a)+a)):
return True
return False
primes = sieve(10000)
# problem solution
def prime_pairs():
# a is first number
for a in primes:
# b is second number
for b in primes:
# check if b is less than a
if b < a:
continue
# check if a and b satisfy the condition
if comb(a, b):
# c is the third number
for c in primes:
# check if c is less than b
if c < b:
continue
# check if a,c and b, c satisfy the condition
if comb(a, c) and comb(b, c):
# d is the fourth number
for d in primes:
# check if d is less than c
if d < c:
continue
# check if (a,d), (b,d) and (c,d) satisfy the condition
if comb(a, d) and comb(b, d) and comb(c, d):
# e is the fifth prime
for e in primes:
# check if e is less than d
if e < d:
continue
# check if (a, e), (b, e), (c, e) and (d, e) satisfy condition
if comb(a, e) and comb(b, e) and comb(c, e) and comb(d, e):
return a+b+c+d+e
print(prime_pairs())