Solution

Answer: 18613426663617118

Let the consecutive primes be $p_1$ and $p_2$, with $p_2 > p_1$.

We seek the smallest integer $S$ such that:

$S \equiv p_1 \pmod{10^d}$, where $d$ is the number of decimal digits of $p_1$,
$S \equiv 0 \pmod{p_2}$.

For example, with $p_1=19$, $p_2=23$:

$$1219 \equiv 19 \pmod{100}, \qquad 1219 \equiv 0 \pmod{23}.$$

We must compute

$$\sum S$$

over all consecutive prime pairs with

$$5 \le p_1 \le 10^6.$$

Mathematical analysis

Suppose $d$ is the number of digits of $p_1$, and define

$$m = 10^d.$$

Any number ending in the digits of $p_1$ can be written as

$$S = m k + p_1$$

for some integer $k \ge 0$.

We require $S$ to be divisible by $p_2$:

$$mk + p_1 \equiv 0 \pmod{p_2}.$$

Thus,

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

Because $p_2$ is prime and $p_2 \ne 2,5$, we have

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

so $m$ has a modular inverse modulo $p_2$. Therefore,

$$k \equiv -p_1 \cdot m^{-1} \pmod{p_2}.$$

The smallest nonnegative solution is

$$k = (-p_1),m^{-1} \bmod p_2.$$

Then

$$S = mk + p_1.$$

So the entire problem reduces to repeated modular inverses.

Computing the modular inverse

Since $p_2$ is prime,

$$m^{-1} \equiv m^{p_2-2} \pmod{p_2}$$

by Fermat's Little Theorem.

Python provides this directly:

pow(m, -1, p2)

which computes the modular inverse efficiently.

Algorithm

Generate all primes up to slightly above $10^6$.
For each consecutive pair $(p_1,p_2)$:

skip $p_1 < 5$,
stop once $p_1 > 10^6$,
let $m = 10^{\text{digits}(p_1)}$,
compute:

$$k = (-p_1)\cdot m^{-1} \bmod p_2,$$

compute:

$$S = mk + p_1,$$

add to total.

Output the total.

The complexity is dominated by the sieve:

$$O(n \log\log n)$$

which is easily fast enough for $10^6$.

Python implementation

from math import isqrt

# ------------------------------------------------------------
# Sieve of Eratosthenes
# ------------------------------------------------------------
def sieve(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, isqrt(limit) + 1):
        if is_prime[i]:
            step = i
            start = i * i
            is_prime[start:limit + 1:step] = [False] * (
                ((limit - start) // step) + 1
            )

    return [i for i, v in enumerate(is_prime) if v]

# We need primes slightly beyond 1,000,000
LIMIT = 1_100_000
primes = sieve(LIMIT)

total = 0

for i in range(len(primes) - 1):
    p1 = primes[i]
    p2 = primes[i + 1]

    if p1 < 5:
        continue

    if p1 > 1_000_000:
        break

    # 10^d where d = number of digits of p1
    m = 10 ** len(str(p1))

    # Solve m*k + p1 ≡ 0 (mod p2)
    inv = pow(m, -1, p2)

    k = (-p1 * inv) % p2

    S = m * k + p1

    total += S

print(total)

Code walkthrough

Prime sieve

def sieve(limit):

Creates all primes up to limit using the Sieve of Eratosthenes.

is_prime[start:limit + 1:step] = ...

Marks multiples of each prime as composite.

Main loop

for i in range(len(primes) - 1):

Iterates through consecutive prime pairs.

p1 = primes[i]
p2 = primes[i + 1]

Defines the consecutive primes.

Constructing numbers ending in $p_1$

m = 10 ** len(str(p1))

If $p_1=19$, then $m=100$.

Thus every candidate is:

$$100k + 19.$$

Modular inverse

inv = pow(m, -1, p2)

Computes $m^{-1} \pmod{p_2}$.

Solving the congruence

k = (-p1 * inv) % p2

This solves:

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

Final value

S = m * k + p1

This is the smallest number satisfying both conditions.

Verification with the example

For $p_1=19$, $p_2=23$:

$$m = 100.$$

We solve:

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

Since

$$100 \equiv 8 \pmod{23},$$

we solve:

$$8k \equiv -19 \equiv 4 \pmod{23}.$$

The inverse of $8$ mod $23$ is $3$, so:

$$k \equiv 12 \pmod{23}.$$

Hence

$$S = 100 \cdot 12 + 19 = 1219,$$

which matches the problem statement.

Final verification

Each $S$ is uniquely determined modulo $10^d p_2$.
The modular inverse always exists because consecutive primes beyond $5$ are coprime to $10$.
The computation is efficient and exact using integer arithmetic only.

Running the code yields:

$$18613426663617118$$

Answer: 18613426663617118

Project Euler Problem 134