Problem 60: Prime Pair Sets

Mathematical Development

Definition 1 (Concatenation). For positive integers $a$ and $b$, define the concatenation

where $d(b) = \lfloor \log_{10} b \rfloor + 1$ is the number of decimal digits of $b$.

Definition 2 (Prime Pair). Primes $p$ and $q$ form a prime pair, written $p \sim q$, if both $p \| q$ and $q \| p$ are prime.

Definition 3 (Prime Pair Set). A set $S$ of primes is a prime pair set of size $k$ if every pair of distinct elements in $S$ satisfies the prime pair relation. Equivalently, $S$ is a clique of size $k$ in the prime pair graph.

Definition 4 (Prime Pair Graph). The prime pair graph is the undirected graph $G = (V, E)$ where $V$ is a set of primes and $\{p, q\} \in E$ if and only if $p \sim q$.

Theorem 1 (Modular Necessary Condition). Let $p, q > 3$ be distinct primes. If $p \not\equiv q \pmod{3}$, then $p \not\sim q$.

Proof. Since $10 \equiv 1 \pmod{3}$, we have $10^d \equiv 1 \pmod{3}$ for all $d \geq 1$. Therefore

For primes $p, q > 3$, we have $p, q \not\equiv 0 \pmod{3}$, so $p \in \{1, 2\} \pmod{3}$ and likewise for $q$. If $p \equiv 1$ and $q \equiv 2$ (or vice versa), then $p + q \equiv 0 \pmod{3}$. Since $p \| q > 3$, divisibility by 3 implies $p \| q$ is composite. By the same argument, $q \| p$ is also composite. Hence $p \not\sim q$. $\square$

Corollary 1 (Residue Class Constraint). In any prime pair set of size $\geq 2$ consisting entirely of primes $> 3$, all elements share the same residue modulo 3.

Proof. Immediate from Theorem 1 applied to each pair. $\square$

Lemma 1 (The Prime 3 is Special). The prime 3 can form a prime pair with primes of either residue class modulo 3. Specifically, for $p > 3$: $3 + p \equiv p \pmod{3}$, which is nonzero since $p \not\equiv 0 \pmod{3}$. Hence the mod-3 obstruction does not apply to pairs involving 3.

Proof. $3 \| p = 3 \cdot 10^{d(p)} + p \equiv 3 + p \equiv p \pmod{3} \not\equiv 0$. Similarly, $p \| 3 = 10p + 3 \equiv p + 3 \equiv p \pmod{3} \not\equiv 0$. So neither concatenation is divisible by 3 (though they may still be composite for other reasons). $\square$

Theorem 2 (Graph-Theoretic Reduction). Finding a prime pair set of size 5 with minimum sum is equivalent to finding a minimum-weight 5-clique in the prime pair graph $G$.

Proof. By Definition 3, a prime pair set of size 5 is a 5-clique in $G$. The sum of the five primes is the weight. Minimizing over all 5-cliques gives the answer. $\square$

Lemma 2 (Search Bound). It suffices to search primes below some bound $B$. If a 5-clique with sum $\Sigma$ is found, then $B = \Sigma$ suffices, since any clique containing a prime $> \Sigma$ has sum $> \Sigma$.

Proof. Each prime in the clique is at most $\Sigma$ (since all five are positive and sum to $\Sigma$). More precisely, the largest prime is at most $\Sigma - 4 \cdot 2 = \Sigma - 8$ (since the smallest prime is 2). In practice, $B = 10{,}000$ is sufficient as confirmed by computation. $\square$

Lemma 3 (Primality of Concatenations). For primes below $B = 10{,}000$, all concatenations satisfy $p \| q < 10^8$. Deterministic Miller-Rabin primality testing with witness set $\{2, 3, 5, 7, 11, 13\}$ is correct for all integers below $3.2 \times 10^{14}$ (Jaeschke, 1993), which amply covers our range.

Proof. The maximum concatenation is $9999 \| 9973 < 10^4 \cdot 10^4 + 10^4 = 10^8 + 10^4 < 3.2 \times 10^{14}$. The cited result guarantees deterministic correctness. $\square$

Theorem 3 (Incremental Clique Search with Pruning). The 5-clique search can be organized as a depth-first enumeration with the following pruning:

(i) Ordering: enumerate clique elements in increasing order $p_1 < p_2 < p_3 < p_4 < p_5$.

(ii) Adjacency intersection: at depth $\ell$, the candidate set for $p_{\ell+1}$ is the intersection of the adjacency lists of $p_1, \ldots, p_\ell$ restricted to elements $> p_\ell$.

(iii) Bound pruning: if the current partial sum plus the minimum possible contribution from remaining elements exceeds the best known sum, prune.

(iv) Mod-3 filter: by Corollary 1, restrict candidates at depth $\geq 2$ to primes sharing the residue class of $p_1$ modulo 3 (unless $p_1 = 3$).

Proof of correctness. (i) avoids redundant permutations. (ii) ensures every pair in the clique is adjacent. (iii) is a standard branch-and-bound argument. (iv) follows from Theorem 1 and Lemma 1. $\square$

Editorial

We first generate the primes below a search bound and build the prime pair graph whose edges correspond to pairs of primes whose two concatenations are both prime. The desired set is then a 5-clique of minimum weight in this graph, so we search for it incrementally: a partial clique is extended only by primes adjacent to all of its current vertices, and branch-and-bound inequalities discard any branch whose best possible completion cannot improve the smallest sum found so far.

Pseudocode

Algorithm: Minimum-sum Prime Pair 5-clique
Require: A prime bound B and a primality test for concatenations below the induced search range.
Ensure: The smallest sum of five primes for which every pair forms a prime pair.
1: Generate the primes below B and build the prime pair graph by connecting distinct primes p and q whenever both p || q and q || p are prime.
2: Search the graph for 5-cliques in increasing prime order, extending each partial clique only by common neighbors and pruning any branch whose optimistic completion already exceeds the best sum found.
3: Return the minimum clique sum obtained.

Complexity Analysis

Theorem 4 (Pair Precomputation Cost). Let $P = \pi(B)$ denote the number of primes below $B$ ($P = 1229$ for $B = 10{,}000$). The adjacency list construction requires $\binom{P}{2} = O(P^2)$ pair tests, each costing $O(\log^2 B)$ with Miller-Rabin. Total: $O(P^2 \log^2 B)$.

Proof. There are $\binom{1229}{2} = 754{,}506$ pairs. Each pair test involves two concatenations and two Miller-Rabin primality tests on numbers up to $10^8$. Each Miller-Rabin test with a constant number of witnesses costs $O(\log^2 n) = O(\log^2 B)$. $\square$

Theorem 5 (Clique Search Cost). The worst-case search is $O(P^5)$, but the pruning from adjacency intersection and bound checks reduces the practical cost to far below this. The dominant cost is the $O(P^2)$ pair precomputation.

Space: $O(P^2)$ for the full adjacency structure, or $O(P \cdot \bar{d})$ using adjacency lists where $\bar{d}$ is the average degree.

Answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// Sieve of Eratosthenes
vector<bool> sieve;
vector<int> primes;

void buildSieve(int n) {
    sieve.assign(n + 1, true);
    sieve[0] = sieve[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (sieve[i]) {
            for (int j = i * i; j <= n; j += i)
                sieve[j] = false;
        }
    }
    for (int i = 2; i <= n; i++)
        if (sieve[i]) primes.push_back(i);
}

// Modular multiplication via __int128 to avoid overflow.
ll mulmod(ll a, ll b, ll m) {
    return (__int128)a * b % m;
}

// Fast modular exponentiation.
ll powmod(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = mulmod(result, base, mod);
        base = mulmod(base, base, mod);
        exp >>= 1;
    }
    return result;
}

// Single round of Miller-Rabin with witness a.
bool millerRabin(ll n, ll a) {
    if (n % a == 0) return n == a;
    ll d = n - 1;
    int r = 0;
    while (d % 2 == 0) { d /= 2; r++; }
    ll x = powmod(a, d, n);
    if (x == 1 || x == n - 1) return true;
    for (int i = 0; i < r - 1; i++) {
        x = mulmod(x, x, n);
        if (x == n - 1) return true;
    }
    return false;
}

// Deterministic primality test.
bool isPrime(ll n) {
    if (n < (int)sieve.size()) return sieve[n];
    if (n < 2) return false;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (ll a : {2, 3, 5, 7, 11, 13}) {
        if (!millerRabin(n, a)) return false;
    }
    return true;
}

// Concatenate a and b: returns a || b = a * 10^{d(b)} + b.
ll concat(ll a, ll b) {
    ll tmp = b, mult = 1;
    while (tmp > 0) { mult *= 10; tmp /= 10; }
    return a * mult + b;
}

// Check if primes a and b form a prime pair.
bool pairCheck(int a, int b) {
    return isPrime(concat(a, b)) && isPrime(concat(b, a));
}

int main() {
    const int LIMIT = 10000;
    buildSieve(LIMIT * 100);  // sieve large enough for concatenations

    int n = primes.size();
    int bound = upper_bound(primes.begin(), primes.end(), LIMIT) - primes.begin();

    // Build adjacency lists
    vector<vector<int>> adj(bound);
    for (int i = 0; i < bound; i++) {
        for (int j = i + 1; j < bound; j++) {
            if (pairCheck(primes[i], primes[j])) {
                adj[i].push_back(j);
            }
        }
    }

    // Fast pair lookup via set
    set<pair<int,int>> pairSet;
    for (int i = 0; i < bound; i++) {
        for (int j : adj[i]) {
            pairSet.insert({i, j});
        }
    }

    auto paired = [&](int i, int j) -> bool {
        if (i > j) swap(i, j);
        return pairSet.count({i, j});
    };

    int bestSum = INT_MAX;

    // Depth-first 5-clique search
    for (int i = 0; i < bound; i++) {
        for (int j : adj[i]) {
            for (int k : adj[j]) {
                if (k <= j) continue;
                if (!paired(i, k)) continue;
                for (int l : adj[k]) {
                    if (l <= k) continue;
                    if (!paired(i, l) || !paired(j, l)) continue;
                    for (int m : adj[l]) {
                        if (m <= l) continue;
                        if (!paired(i, m) || !paired(j, m) || !paired(k, m)) continue;
                        int s = primes[i] + primes[j] + primes[k] + primes[l] + primes[m];
                        bestSum = min(bestSum, s);
                    }
                }
            }
        }
    }

    cout << bestSum << endl;
    return 0;
}

"""
Project Euler Problem 60: Prime Pair Sets

Find the lowest sum for a set of five primes for which any two
primes concatenate (in either order) to produce another prime.

Approach: build the prime-pair graph and search for minimum-weight
5-cliques via depth-first enumeration with adjacency-intersection
pruning and branch-and-bound.

Answer: 26033
"""
from sympy import isprime, primerange

def solve():
    LIMIT = 10000
    primes = list(primerange(2, LIMIT))

    pair_cache = {}

    def is_pair(a, b):
        key = (a, b)
        if key not in pair_cache:
            pair_cache[key] = (
                isprime(int(str(a) + str(b))) and
                isprime(int(str(b) + str(a)))
            )
        return pair_cache[key]

    # Build adjacency lists
    adj = {p: [] for p in primes}
    for i in range(len(primes)):
        for j in range(i + 1, len(primes)):
            if is_pair(primes[i], primes[j]):
                adj[primes[i]].append(primes[j])

    best = float('inf')

    # Incremental 5-clique search
    for p1 in primes:
        if p1 * 5 >= best:
            break
        for p2 in adj[p1]:
            if p1 + p2 * 4 >= best:
                break
            friends2 = [p for p in adj[p1] if p > p2 and is_pair(p2, p)]
            for p3 in friends2:
                if p1 + p2 + p3 * 3 >= best:
                    break
                friends3 = [p for p in friends2 if p > p3 and is_pair(p3, p)]
                for p4 in friends3:
                    if p1 + p2 + p3 + p4 * 2 >= best:
                        break
                    friends4 = [p for p in friends3 if p > p4 and is_pair(p4, p)]
                    for p5 in friends4:
                        s = p1 + p2 + p3 + p4 + p5
                        if s < best:
                            best = s

    return best

if __name__ == "__main__":
    answer = solve()
assert answer == 26033
print(answer)