Solution

Answer: 26033

We seek the lowest-sum set of five primes such that for any two distinct primes $p,q$ in the set, both concatenations

$$pq \quad \text{and} \quad qp$$

are prime.

For example, the set ${3,7,109,673}$ works for size $4$, with sum $792$.

We now solve the size $5$ case.

Mathematical Analysis

1. Concatenation as arithmetic

If $a$ has $d$ decimal digits, concatenating $p$ followed by $a$ gives

$$p | a = p \cdot 10^d + a$$

Example:

$$7 | 109 = 7 \cdot 10^3 + 109 = 7109$$

Thus, for every pair $(p,q)$, we must test:

$$p \cdot 10^{\text{digits}(q)} + q$$

and

$$q \cdot 10^{\text{digits}(p)} + p$$

for primality.

2. Graph interpretation

This problem becomes much easier if viewed as a graph problem.

Each prime is a vertex.
Connect primes $p,q$ with an edge if both concatenations are prime.

We seek a clique of size 5 (a fully connected set of five vertices) with minimum sum.

This dramatically reduces the search space.

3. Important observations

(a) Excluding 2 and 5

Any concatenation ending in an even digit is even.

So if a set contains $2$, then some concatenation ends in $2$, making it composite.

Likewise, concatenations ending in $5$ are divisible by $5$.

Therefore:

$$2,5 \text{ cannot appear in the set}$$

(b) Efficient primality testing

Concatenations become fairly large, so we need a fast primality test.

For Project Euler scales, trial division up to $\sqrt n$ with a precomputed prime list is sufficient.

4. Search strategy

We proceed as follows:

Generate primes.
Build compatibility relations:

$$compatible(p,q) \iff pq \text{ and } qp \text{ are prime}$$ 3. Use nested intersections (clique search):

choose $a$
choose $b$ compatible with $a$
choose $c$ compatible with both
etc.

Because intersections shrink rapidly, the search becomes feasible.

Python Implementation

from math import isqrt

# ------------------------------------------------------------
# Basic primality test
# ------------------------------------------------------------

def is_prime(n):
    """Return True if n is prime."""
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2

    limit = isqrt(n)
    d = 3
    while d <= limit:
        if n % d == 0:
            return False
        d += 2

    return True

# ------------------------------------------------------------
# Concatenation helper
# ------------------------------------------------------------

def concat(a, b):
    """Concatenate integers a and b."""
    return int(str(a) + str(b))

# ------------------------------------------------------------
# Compatibility test
# ------------------------------------------------------------

def compatible(a, b):
    """
    Two primes are compatible if both concatenations
    are prime.
    """
    return is_prime(concat(a, b)) and is_prime(concat(b, a))

# ------------------------------------------------------------
# Generate primes
# ------------------------------------------------------------

def generate_primes(limit):
    """Simple sieve of Eratosthenes."""
    sieve = [True] * limit
    sieve[0] = sieve[1] = False

    for i in range(2, isqrt(limit) + 1):
        if sieve[i]:
            step = i
            start = i * i
            sieve[start:limit:step] = [False] * len(range(start, limit, step))

    return [p for p in range(limit) if sieve[p]]

# ------------------------------------------------------------
# Main search
# ------------------------------------------------------------

primes = [p for p in generate_primes(10000) if p not in (2, 5)]

# Build compatibility graph
edges = {}

for i, p in enumerate(primes):
    edges[p] = set()

    for q in primes[:i]:
        if compatible(p, q):
            edges[p].add(q)
            edges[q].add(p)

best_sum = float('inf')
best_set = None

# Clique search of size 5
for a in primes:

    for b in edges[a]:

        ab = edges[a] & edges[b]

        for c in ab:

            abc = ab & edges[c]

            for d in abc:

                abcd = abc & edges[d]

                for e in abcd:

                    s = a + b + c + d + e

                    if s < best_sum:
                        best_sum = s
                        best_set = [a, b, c, d, e]

print(best_set)
print(best_sum)

Code Walkthrough

Primality testing

def is_prime(n):

Checks whether $n$ is prime using trial division up to:

$$\sqrt n$$

We skip even divisors for speed.

Concatenation

def concat(a, b):
    return int(str(a) + str(b))

Turns $a=7$, $b=109$ into:

$$7109$$

Compatibility

compatible(a, b)

Verifies:

$$ab \text{ and } ba$$

are both prime.

Sieve generation

generate_primes(10000)

Creates all primes below $10000$.

This is enough for the minimal solution.

Building the graph

edges[p].add(q)

Stores all primes compatible with $p$.

Clique search

The key optimization is repeated intersection:

ab = edges[a] & edges[b]

meaning:

candidates compatible with both $a$ and $b$

Then:

abc = ab & edges[c]

meaning:

compatible with $a,b,c$

and so on.

This avoids brute force over all 5-tuples.

Verifying the Example

For the problem’s example:

$${3,7,109,673}$$

we verify:

$7 | 109 = 7109$ is prime
$109 | 7 = 1097$ is prime

and similarly for every pair.

Their sum:

$$3+7+109+673=792$$

matches the statement.

Final Verification

The algorithm finds the minimal 5-prime clique:

$${13, 5197, 5701, 6733, 8389}$$

Checking the sum:

$$13 + 5197 + 5701 + 6733 + 8389 = 26033$$

This is the known Project Euler result and satisfies all pairwise concatenation conditions.

Answer: 26033

Project Euler Problem 60