Problem 425: Prime Connection

View on Project Euler

Project Euler Problem 425 Solution

EulerSolve provides an optimized solution for Project Euler Problem 425, Prime Connection, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Fix a limit \(L\). We look at the primes up to \(L\), and we connect two primes when one legal decimal edit turns one into the other while staying prime. The allowed edits are: replace one digit without creating a leading zero, delete the most significant digit, or prepend one new nonzero digit. The required sum is not over all unreachable primes in the full graph. For each prime \(p\), we only allow primes \(\le p\) as intermediate vertices. A prime contributes exactly when 2 is still disconnected from \(p\) inside that restricted graph. Mathematical Approach Step 1: The Prime Edit Graph Let \(\mathbb{P}\) denote the set of primes and define $$V_L=\mathbb{P}\cap [2,L].$$ We build an undirected graph \(G_L=(V_L,E_L)\). An edge joins two primes if one can be obtained from the other by exactly one allowed decimal edit. Replacing a digit is symmetric, and deleting the leading digit is the inverse of prepending a leading digit, so the graph may be treated as undirected. If a prime has \(d\) digits, then its neighbors are generated by three families of moves: 1. change one of the \(d\) digits to another digit, with the restriction that the first digit cannot become 0; 2. if \(d \ge 2\), remove the first digit; 3. prepend one digit from 1 through 9. Only prime results remain in the graph....

Detailed mathematical approach

Problem Summary

Fix a limit \(L\). We look at the primes up to \(L\), and we connect two primes when one legal decimal edit turns one into the other while staying prime. The allowed edits are: replace one digit without creating a leading zero, delete the most significant digit, or prepend one new nonzero digit.

The required sum is not over all unreachable primes in the full graph. For each prime \(p\), we only allow primes \(\le p\) as intermediate vertices. A prime contributes exactly when 2 is still disconnected from \(p\) inside that restricted graph.

Mathematical Approach

Step 1: The Prime Edit Graph

Let \(\mathbb{P}\) denote the set of primes and define

$$V_L=\mathbb{P}\cap [2,L].$$

We build an undirected graph \(G_L=(V_L,E_L)\). An edge joins two primes if one can be obtained from the other by exactly one allowed decimal edit. Replacing a digit is symmetric, and deleting the leading digit is the inverse of prepending a leading digit, so the graph may be treated as undirected.

If a prime has \(d\) digits, then its neighbors are generated by three families of moves:

1. change one of the \(d\) digits to another digit, with the restriction that the first digit cannot become 0;

2. if \(d \ge 2\), remove the first digit;

3. prepend one digit from 1 through 9.

Only prime results remain in the graph.

Step 2: Reformulate the Condition with Threshold Graphs

For every threshold \(t \le L\), let \(G_{\le t}\) be the induced subgraph on

$$V_t=\mathbb{P}\cap [2,t].$$

Write \(2 \sim_t p\) when 2 and \(p\) are connected in \(G_{\le t}\). Then the problem asks for

$$S(L)=\sum_{\substack{p\in\mathbb{P}\\ p\le L\\ 2 \not\sim_p p}} p.$$

So each prime has its own threshold: we do not ask whether \(p\) is connected to 2 somewhere in the full graph up to \(L\), but whether it is already connected at the moment the graph is truncated at \(p\).

Step 3: Convert the Problem to a Minimax Path Value

Define \(\tau(p)\) as the smallest threshold \(t\) such that \(2 \sim_t p\). Equivalently, for any path

$$P=(q_0=2,q_1,\dots,q_k=p),$$

define its bottleneck value by

$$B(P)=\max_{0\le i\le k} q_i.$$

Then

$$\tau(p)=\min_{P:2\leadsto p} B(P).$$

This identity is the key reduction. If a path has bottleneck \(M\), then every vertex of that path lies in \(G_{\le M}\), so \(2 \sim_M p\). Conversely, if \(2 \sim_t p\), some path in \(G_{\le t}\) connects them, and that path has maximum vertex at most \(t\). Therefore the minimum threshold and the minimum bottleneck are the same quantity.

The contribution test now becomes simply

$$\tau(p)>p.$$

In words: every path from 2 to \(p\) is forced to pass through some prime strictly larger than \(p\).

Step 4: Dijkstra with a Bottleneck Relaxation

The minimax value \(\tau(p)\) can be computed by the same greedy structure as Dijkstra's algorithm. Instead of ordinary path length, each vertex stores its best known bottleneck value. Start with label 2 at the vertex 2 and \(+\infty\) elsewhere.

Suppose a prime \(u\) has already been reached with current label \(d(u)\), and \(v\) is a prime neighbor of \(u\). Any path to \(u\) with bottleneck \(d(u)\) extends to a path to \(v\) with bottleneck

$$\max(d(u),v).$$

Hence the relaxation rule is

$$d(v)\leftarrow \min\bigl(d(v),\max(d(u),v)\bigr).$$

This works because extending a path cannot decrease its bottleneck. The labels are monotone, so once the smallest tentative label is extracted from the priority queue, no later path can improve it. That is exactly the usual correctness argument for Dijkstra, with addition replaced by \(\max\).

Worked Example

The prime 11 is the first nontrivial example. There is a path

$$2 \to 3 \to 13 \to 11,$$

so \(\tau(11)\le 13\). On the other hand, in the threshold graph \(G_{\le 11}\), the vertex 11 has no valid incident edge: every legal one-step edit gives either a non-prime, a number with a leading zero, or a prime greater than 11. Therefore \(2 \not\sim_{11} 11\), and

$$\tau(11)=13>11.$$

So 11 contributes to the sum.

The same minimax search shows

$$\tau(101)=\tau(103)=\tau(107)=\tau(109)=113.$$

Hence the contributing primes below \(10^3\) are

$$11,\ 101,\ 103,\ 107,\ 109,$$

and therefore

$$S(10^3)=11+101+103+107+109=431.$$

This matches the checkpoint used by the implementation. A second checkpoint is

$$S(10^4)=78728.$$

How the Code Works

The C++, Python, and Java implementations first build a sieve of Eratosthenes up to \(L\), so primality tests become constant-time table lookups. They also precompute powers of 10 in order to address decimal positions directly.

The graph is never materialized in full. Instead, whenever the priority queue extracts a prime, the implementation generates all valid one-step edits of its decimal representation: same-length digit replacements, deletion of the most significant digit, and prepending of one nonzero digit. Every candidate is tested against the sieve, and prime candidates are relaxed with the bottleneck update above.

After the queue is exhausted, each prime \(p\) has its final threshold value \(\tau(p)\). The program then scans the prime list once and accumulates exactly those primes with \(\tau(p)>p\).

Complexity Analysis

Let

$$V=\pi(L),\qquad D=\lfloor \log_{10} L \rfloor + 1.$$

The sieve costs \(O(L\log\log L)\) time and \(O(L)\) memory. For each extracted prime, neighbor generation inspects at most \(9D\) replacements, one deletion, and up to nine prepends, so the implicit graph contributes \(E=O(VD)\) candidate relaxations. The priority queue phase therefore costs

$$O(E\log V)=O(VD\log V).$$

The total complexity is

$$O(L\log\log L + VD\log V)$$

time and \(O(L)\) memory, which is efficient enough for the required limit.

Footnotes and References

  1. Problem page: https://projecteuler.net/problem=425
  2. Dijkstra's algorithm: Wikipedia — Dijkstra's algorithm
  3. Bottleneck / minimax paths: Wikipedia — Widest path problem
  4. Sieve of Eratosthenes: Wikipedia — Sieve of Eratosthenes
  5. Graph theory background: Wikipedia — Graph theory

Problem 425 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <queue>
#include <string>
#include <vector>

namespace {

using i64 = long long;

struct Options {
    int limit = 10000000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    try {
        value = std::stoi(tail);
    } catch (...) {
        return false;
    }
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 2;
}

std::vector<uint8_t> sieve_is_prime(int n) {
    std::vector<uint8_t> is_prime(static_cast<std::size_t>(n + 1), 1);
    is_prime[0] = 0;
    is_prime[1] = 0;
    for (int p = 2; 1LL * p * p <= n; ++p) {
        if (!is_prime[static_cast<std::size_t>(p)]) {
            continue;
        }
        for (int q = p * p; q <= n; q += p) {
            is_prime[static_cast<std::size_t>(q)] = 0;
        }
    }
    return is_prime;
}

i64 S_value(int limit) {
    const std::vector<uint8_t> is_prime = sieve_is_prime(limit);

    std::vector<int> primes;
    primes.reserve(limit / 10);
    for (int x = 2; x <= limit; ++x) {
        if (is_prime[static_cast<std::size_t>(x)]) {
            primes.push_back(x);
        }
    }

    std::vector<int> pow10{1};
    while (pow10.back() <= limit / 10) {
        pow10.push_back(pow10.back() * 10);
    }

    const int INF = std::numeric_limits<int>::max();
    std::vector<int> best(static_cast<std::size_t>(limit + 1), INF);
    if (limit < 2 || !is_prime[2]) {
        return 0;
    }

    using Node = std::pair<int, int>;  // (minimax cost, prime)
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> pq;
    best[2] = 2;
    pq.push({2, 2});

    auto relax = [&](int from_cost, int v) {
        if (v < 2 || v > limit || !is_prime[static_cast<std::size_t>(v)]) {
            return;
        }
        const int cand = std::max(from_cost, v);
        if (cand < best[static_cast<std::size_t>(v)]) {
            best[static_cast<std::size_t>(v)] = cand;
            pq.push({cand, v});
        }
    };

    while (!pq.empty()) {
        const auto [cost, p] = pq.top();
        pq.pop();
        if (cost != best[static_cast<std::size_t>(p)]) {
            continue;
        }

        int len = 1;
        while (len < static_cast<int>(pow10.size()) && p >= pow10[len]) {
            ++len;
        }

        for (int pos = 0; pos < len; ++pos) {
            const int place = pow10[pos];
            const int old_digit = (p / place) % 10;
            for (int d = 0; d <= 9; ++d) {
                if (d == old_digit) {
                    continue;
                }
                if (pos == len - 1 && d == 0) {
                    continue;  // no leading zero
                }
                const int v = p + (d - old_digit) * place;
                relax(cost, v);
            }
        }

        if (len > 1) {
            const int v = p % pow10[len - 1];
            relax(cost, v);
        }

        if (len < static_cast<int>(pow10.size())) {
            const int base = pow10[len];
            for (int d = 1; d <= 9; ++d) {
                const i64 v = static_cast<i64>(d) * base + p;
                if (v > limit) {
                    break;
                }
                relax(cost, static_cast<int>(v));
            }
        }
    }

    i64 ans = 0;
    for (const int p : primes) {
        if (best[static_cast<std::size_t>(p)] > p) {
            ans += p;
        }
    }
    return ans;
}

bool run_checkpoints() {
    if (S_value(1000) != 431LL) {
        std::cerr << "Checkpoint failed: S(10^3)\n";
        return false;
    }
    if (S_value(10000) != 78728LL) {
        std::cerr << "Checkpoint failed: S(10^4)\n";
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << S_value(options.limit) << '\n';
    return 0;
}

Python

import heapq

def solve():
    LIMIT = 10_000_000

    # Sieve of Eratosthenes
    is_prime = bytearray([1]) * (LIMIT + 1)
    is_prime[0] = is_prime[1] = 0
    for p in range(2, int(LIMIT**0.5) + 1):
        if is_prime[p]:
            for q in range(p*p, LIMIT+1, p):
                is_prime[q] = 0

    pow10 = [1]
    while pow10[-1] <= LIMIT // 10:
        pow10.append(pow10[-1] * 10)

    INF = float('inf')
    best = [INF] * (LIMIT + 1)
    best[2] = 2
    pq = [(2, 2)]

    while pq:
        cost, p = heapq.heappop(pq)
        if cost != best[p]: continue

        ln = 1
        while ln < len(pow10) and p >= pow10[ln]:
            ln += 1

        # Change one digit
        for pos in range(ln):
            place = pow10[pos]
            old_d = (p // place) % 10
            for d in range(10):
                if d == old_d: continue
                if pos == ln - 1 and d == 0: continue
                v = p + (d - old_d) * place
                if 2 <= v <= LIMIT and is_prime[v]:
                    cand = max(cost, v)
                    if cand < best[v]:
                        best[v] = cand
                        heapq.heappush(pq, (cand, v))

        # Remove leading digit
        if ln > 1:
            v = p % pow10[ln - 1]
            if 2 <= v <= LIMIT and is_prime[v]:
                cand = max(cost, v)
                if cand < best[v]:
                    best[v] = cand
                    heapq.heappush(pq, (cand, v))

        # Prepend digit
        if ln < len(pow10):
            base = pow10[ln]
            for d in range(1, 10):
                v = d * base + p
                if v > LIMIT: break
                if is_prime[v]:
                    cand = max(cost, v)
                    if cand < best[v]:
                        best[v] = cand
                        heapq.heappush(pq, (cand, v))

    ans = sum(p for p in range(2, LIMIT+1) if is_prime[p] and best[p] > p)
    return str(ans)

if __name__ == '__main__':
    print(solve())

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Euler425 {

    static boolean[] sievePrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        if (n >= 2) {
            Arrays.fill(isPrime, 2, n + 1, true);
        }
        for (int p = 2; p * p <= n; p++) {
            if (isPrime[p]) {
                for (int q = p * p; q <= n; q += p) {
                    isPrime[q] = false;
                }
            }
        }
        return isPrime;
    }

    static class Node implements Comparable<Node> {
        int cost;
        int p;

        Node(int cost, int p) {
            this.cost = cost;
            this.p = p;
        }

        @Override
        public int compareTo(Node o) {
            if (this.cost != o.cost) {
                return Integer.compare(this.cost, o.cost);
            }
            return Integer.compare(this.p, o.p);
        }
    }

    static String solveS(int limit) {
        boolean[] isPrime = sievePrimes(limit);
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= limit; i++) {
            if (isPrime[i])
                primes.add(i);
        }

        List<Integer> pow10 = new ArrayList<>();
        pow10.add(1);
        while (pow10.get(pow10.size() - 1) <= limit / 10) {
            pow10.add(pow10.get(pow10.size() - 1) * 10);
        }

        int[] best = new int[limit + 1];
        Arrays.fill(best, Integer.MAX_VALUE);
        if (limit < 2 || !isPrime[2])
            return "0";

        PriorityQueue<Node> pq = new PriorityQueue<>();
        best[2] = 2;
        pq.add(new Node(2, 2));

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int cost = node.cost;
            int p = node.p;
            if (cost != best[p])
                continue;

            int len = 1;
            while (len < pow10.size() && p >= pow10.get(len)) {
                len++;
            }

            for (int pos = 0; pos < len; pos++) {
                int place = pow10.get(pos);
                int oldDigit = (p / place) % 10;
                for (int d = 0; d <= 9; d++) {
                    if (d == oldDigit)
                        continue;
                    if (pos == len - 1 && d == 0)
                        continue;
                    int v = p + (d - oldDigit) * place;

                    if (v >= 2 && v <= limit && isPrime[v]) {
                        int cand = Math.max(cost, v);
                        if (cand < best[v]) {
                            best[v] = cand;
                            pq.add(new Node(cand, v));
                        }
                    }
                }
            }

            if (len > 1) {
                int v = p % pow10.get(len - 1);
                if (v >= 2 && v <= limit && isPrime[v]) {
                    int cand = Math.max(cost, v);
                    if (cand < best[v]) {
                        best[v] = cand;
                        pq.add(new Node(cand, v));
                    }
                }
            }

            if (len < pow10.size()) {
                int base = pow10.get(len);
                for (int d = 1; d <= 9; d++) {
                    long vl = (long) d * base + p;
                    if (vl <= limit) {
                        int v = (int) vl;
                        if (v >= 2 && isPrime[v]) {
                            int cand = Math.max(cost, v);
                            if (cand < best[v]) {
                                best[v] = cand;
                                pq.add(new Node(cand, v));
                            }
                        }
                    }
                }
            }
        }

        long ans = 0;
        for (int p : primes) {
            if (best[p] > p) {
                ans += p;
            }
        }
        return Long.toString(ans);
    }

    public static void main(String[] args) {
        System.out.println(solveS(10000000));
    }
}