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