Detailed mathematical approach

Problem Summary

We seek five distinct primes with the property that every unordered pair \(\{p,q\}\) stays prime after concatenation in both directions. If \(p=7\) and \(q=109\), for example, then both \(7109\) and \(1097\) must be prime. Among all such 5-element sets, the goal is to minimize the sum of the five primes.

The implementations search primes below a configurable limit, with \(10{,}000\) as the default for the Euler instance. A smaller benchmark is already known: \(\{3,7,109,673\}\) satisfies the same pairwise condition for four primes and has sum \(792\), so any correct full solution should at least reproduce that checkpoint.

Mathematical Approach

Let \(\mathcal{P}\) be the candidate primes below the search limit after removing values that can never belong to a valid pair. Define a symmetric compatibility relation \(p \sim q\) when both concatenations are prime. Problem 60 then becomes a minimum-weight clique problem on an undirected graph whose vertex weight is the prime itself.

Concatenation as Arithmetic

If \(d(q)\) denotes the number of decimal digits of \(q\), then

$\operatorname{concat}(p,q)=p\cdot 10^{d(q)}+q,\qquad d(q)=\lfloor \log_{10} q \rfloor + 1.$

So an edge test is purely arithmetic: for a pair \(p,q\), compute \(\operatorname{concat}(p,q)\) and \(\operatorname{concat}(q,p)\), and ask whether both are prime. With the default limit \(10{,}000\), every candidate has at most four digits, so the largest concatenations stay below \(10^8\); the implementations nevertheless use a 64-bit primality test so that larger optional limits remain safe.

Why \(2\) and \(5\) Never Appear

The search discards \(2\) and \(5\) completely, and this is a theorem, not a heuristic. If \(q\) is any other prime, then \(\operatorname{concat}(q,2)\) ends in \(2\) and is larger than \(2\), so it is composite. Likewise \(\operatorname{concat}(q,5)\) ends in \(5\) and is larger than \(5\), so it is composite. Since a valid pair requires primality in both directions, no set of size at least \(2\) can contain \(2\) or \(5\).

Turn the Problem into a Graph

Build an undirected graph \(G\) with vertex set \(\mathcal{P}\), and join \(p\) and \(q\) by an edge exactly when \(p \sim q\). A valid set of five primes is then a 5-clique in \(G\): every two chosen vertices are adjacent because every required concatenation test succeeds.

The objective is not merely to find any 5-clique, but to minimize

$w(C)=\sum_{p\in C} p.$

All vertex weights are positive, so partial sums already provide useful information for pruning: once a partial choice is too large, no extension can improve it.

Recursive Search State and Invariant

The implementations use depth-first search on partial cliques. A recursive state consists of a chosen set \(C\), a candidate list \(R\), and the current sum \(s(C)\). The key invariant is

$\text{every } r\in R \text{ is larger than all primes in } C \text{ and is adjacent to every element of } C.$

Because primes are processed in increasing order, each clique is generated exactly once. If the next chosen prime is \(v\in R\), the recursive call keeps only those later candidates that remain compatible with the enlarged clique:

$R_v=\{u\in R:u>v \text{ and } u\sim x \text{ for all } x\in C\cup\{v\}\}.$

Reaching \(\lvert C\rvert=5\) produces a valid solution, and its sum is compared against the best sum found so far.

Why the Pruning is Correct

Two pruning rules in the code are mathematically safe. First, if \(\lvert R\rvert < 5-\lvert C\rvert\), then there are not enough remaining vertices to finish a 5-clique, so the branch is impossible. Second, if \(s(C)+v\geq S_{\mathrm{best}}\) for the next candidate \(v\), then every continuation of that branch has sum at least \(s(C)+v\), hence at least the best sum already found. Because all primes are positive, the branch can be discarded immediately.

This is a branch-and-bound argument specialized to a weighted clique search with positive vertex weights and an increasing-order traversal.

Worked Example: the Four-Prime Checkpoint

The set

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

is a 4-clique. For instance, \(3\) and \(109\) work because \(3109\) and \(1093\) are prime, while \(7\) and \(673\) work because \(7673\) and \(6737\) are prime. The same holds for the remaining four unordered pairs, so every pair inside the set is compatible.

Its sum is

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

The implementations use this fact as a checkpoint for the smaller task of finding the minimum-sum 4-clique below \(1000\). The full Euler problem has exactly the same structure, just one level deeper: extend the search from 4 compatible primes to 5.

How the Code Works

Prime Generation and Primality Testing

The C++, Python, and Java implementations first sieve all primes up to the chosen limit and omit \(2\) and \(5\). Every concatenated number is then tested with a deterministic 64-bit Miller-Rabin routine, after first checking divisibility by a short list of small primes. That combination is fast for the Euler input and remains correct if the search limit is raised.

Building the Compatibility Matrix

After the prime list is prepared, the implementation checks each unordered pair once. If both concatenations are prime, the pair is recorded in a symmetric compatibility matrix. For the default limit \(10{,}000\), there are \(1227\) retained primes, so this stage performs

$\binom{1227}{2}=752151$

pair tests, each consisting of two primality checks.

Depth-First Clique Extension

The search starts with an empty clique and the full sorted prime list. At each level it picks one candidate, adds its value to the running sum, and scans only later candidates. A later prime survives to the next recursive call exactly when it is compatible with every currently chosen prime, which preserves the clique invariant at all times.

When five primes have been chosen, the implementation updates the best sum. It does not need to store the full best set to answer the Euler question, because the required output is the minimum sum alone.

Checkpoint and Final Run

Before solving the full instance, the implementations optionally verify the known 4-prime checkpoint \(792\). This guards against errors in concatenation arithmetic, primality testing, and recursive clique construction. Once that test passes, the same search logic runs with target size \(5\) and the default prime limit.

Complexity Analysis

Let \(P=\lvert\mathcal{P}\rvert\) be the number of retained primes and let \(T\) denote the cost of one primality test. Building the compatibility matrix costs \(O(P^2T)\) time and \(O(P^2)\) space, because every unordered pair is tested once and the result is stored in a full symmetric table.

The recursive search is output-sensitive: its exact cost depends on how sparse the compatibility graph is. In the densest conceivable case with target size \(5\), it can behave like \(O(P^5)\), but the actual graph is sparse and each recursive call sharply shrinks the candidate list. The extra search memory beyond the matrix is only the recursion stack and temporary candidate lists, so the dominating storage term remains the \(O(P^2)\) compatibility table.

Footnotes and References

1. Problem statement: Project Euler 60 - Prime pair sets
2. Prime numbers: Wikipedia - Prime number
3. Miller-Rabin primality test: Wikipedia - Miller-Rabin primality test
4. Cliques in graph theory: Wikipedia - Clique
5. Branch and bound: Wikipedia - Branch and bound