Detailed mathematical approach

Problem Summary

For each pair of consecutive primes \(p_1, p_2\) with \(5 \le p_1 \le 10^6\), let \(S(p_1,p_2)\) be the smallest positive integer that is divisible by \(p_2\) and whose decimal expansion ends with the digits of \(p_1\). The task is to sum \(S(p_1,p_2)\) over all such consecutive prime pairs.

A brute-force scan through multiples of \(p_2\) would be wasteful. The suffix condition is really a congruence modulo a power of ten, so every prime pair can be solved by one modular inverse and one multiplication.

Mathematical Approach

Let \(d\) be the number of decimal digits of \(p_1\), and set \(M = 10^d\). Saying that a number ends with the digits of \(p_1\) is equivalent to saying that it is congruent to \(p_1\) modulo \(M\).

Write the unknown number as a multiple of the next prime

If \(n\) is divisible by \(p_2\), then \(n = p_2 k\) for some positive integer \(k\). The suffix requirement becomes

$p_2 k \equiv p_1 \pmod{M}.$

This is the central congruence used by the implementations. It solves directly for the multiplier \(k\), and then reconstructs \(n\) as \(p_2 k\).

Why a modular inverse exists

Because \(p_1 \ge 5\) and \(p_2\) is the next prime, we always have \(p_2 \ge 7\). Therefore \(p_2\) is not divisible by 2 or 5, while \(M = 10^d\) has no prime factors other than 2 and 5. Hence

$\gcd(p_2, M) = 1,$

so \(p_2\) has a unique multiplicative inverse modulo \(M\). Multiplying the congruence by that inverse gives

$k \equiv p_1 \, p_2^{-1} \pmod{M}.$

The least residue gives the smallest admissible number

Let \(k_0\) be the least positive residue of \(p_1 p_2^{-1}\) modulo \(M\). Then every valid multiplier has the form

$k = k_0 + tM \qquad (t \ge 0),$

and every valid number has the form

$n = p_2(k_0 + tM) = p_2 k_0 + t(p_2 M).$

Since the step size \(p_2 M\) is positive, the smallest valid number is obtained at \(t = 0\). Therefore

$\boxed{S(p_1,p_2) = p_2 \left( (p_1 p_2^{-1}) \bmod M \right).}$

This is exactly the value accumulated by the C++, Python, and Java implementations.

Worked example: \(p_1 = 19\), \(p_2 = 23\)

Here \(d = 2\), so \(M = 100\). We need

$23k \equiv 19 \pmod{100}.$

The inverse of \(23\) modulo \(100\) is \(87\), because \(23 \cdot 87 = 2001 \equiv 1 \pmod{100}\). Hence

$k_0 \equiv 19 \cdot 87 \equiv 53 \pmod{100},$

so the smallest valid number is

$S(19,23) = 23 \cdot 53 = 1219.$

And indeed \(1219\) is divisible by \(23\) and ends in the digits \(19\).

An equivalent but different derivation

One can also write \(n = p_1 + Mt\) and solve

$Mt \equiv -p_1 \pmod{p_2}.$

That version uses the inverse of \(M\) modulo \(p_2\). It is mathematically equivalent, but the implementations choose the dual viewpoint above because they already represent the answer as a multiple of \(p_2\).

How the Code Works

Prime generation

The implementations first generate primes beyond \(10^6\), not merely up to \(10^6\), because every prime \(p_1\) below the bound needs its consecutive successor \(p_2\). They then scan the prime list pair by pair and stop once \(p_1\) reaches the limit.

Per-pair arithmetic

For each pair, the implementation computes \(M = 10^d\) by counting the decimal digits of \(p_1\). Since \(p_1 \lt 10^6\), we only need \(d \le 6\). It then computes the inverse of \(p_2 \bmod M\): the C++ version does this with the extended Euclidean algorithm, the Python version uses built-in modular inversion, and the Java version uses big-integer modular inversion.

After that, the implementation forms the least residue \(k_0 = (p_1 p_2^{-1}) \bmod M\), multiplies by \(p_2\), and adds the result to the running sum. No candidate values are tested, and no repeated multiples are scanned.

Complexity Analysis

If the sieve bound is \(L\), prime generation costs \(O(L \log \log L)\) time and \(O(L)\) memory. After the sieve, each consecutive prime pair requires only a digit count and one modular inverse modulo \(10^d\), so the per-pair work is \(O(\log M)\) with \(M \le 10^6\), effectively very small here.

In practice the sieve dominates the runtime, while the arithmetic for each pair is tiny. The total sum also fits comfortably in signed 64-bit arithmetic for the stated bound, which is why the fixed-width implementations can accumulate it directly.

Footnotes and References

1. Problem page: Project Euler 134 - Prime pair connection
2. Modular multiplicative inverse: Wikipedia - Modular multiplicative inverse
3. Linear congruence theorem: Wikipedia - Linear congruence theorem
4. Extended Euclidean algorithm: Wikipedia - Extended Euclidean algorithm
5. Sieve of Eratosthenes: Wikipedia - Sieve of Eratosthenes