Project Euler Problem 425

Solution

Answer: 46479497324

Let a prime $P$ be reachable from $2$ by a chain of connected primes such that no prime in the chain exceeds $P$. The key observation is that this is a minimax path problem on a graph of primes.

Define a graph whose vertices are primes, with an edge $A \leftrightarrow B$ whenever:

$A,B$ have the same number of digits and differ in exactly one digit, or
one is obtained from the other by adding/removing a single leading digit.

For any prime $p$, define

$$m(p)=\min_{\text{paths }2\to p}\ \max(\text{prime on path})$$

Then:

$p$ is a 2’s relative iff $m(p)=p$,
$p$ is not a 2’s relative iff $m(p)>p$.

This converts the problem into computing the minimax value $m(p)$ for all primes $p\le 10^7$.

The natural algorithm is a Dijkstra-style propagation where the “distance” is:

$$\text{cost}(u\to v)=\max(m(u),v)$$

Because all costs are monotone, repeatedly relaxing neighbors computes the minimal possible maximum prime on a path.

I verified the implementation against the problem’s checks:

$F(10^3)=431$
$F(10^4)=78728$

both exactly matching the statement.

Running the full computation for $10^7$ gives:

Answer: 46479497324