Problem 134: Prime Pair Connection

Mathematical Foundation

Theorem 1. Let $p_1$ have $d$ digits, so $10^{d-1} \leq p_1 < 10^d$. Then:

where $k = (-p_1 \cdot (10^d)^{-1}) \bmod p_2$, and $(10^d)^{-1}$ is the modular inverse of $10^d$ modulo $p_2$.

Proof. We seek the smallest positive integer $S \equiv p_1 \pmod{10^d}$ with $p_2 \mid S$. Write $S = p_1 + k \cdot 10^d$ for $k \geq 0$. The divisibility condition becomes:

Since $p_2$ is an odd prime greater than 5, $\gcd(10^d, p_2) = 1$, so the modular inverse exists. Solving: $k \equiv -p_1 \cdot (10^d)^{-1} \pmod{p_2}$. Taking the least non-negative residue gives the unique $k \in \{0, 1, \ldots, p_2 - 1\}$.

We claim $k \geq 1$. If $k = 0$, then $S = p_1$ and $p_2 \mid p_1$. But $p_2 > p_1$ (consecutive primes with $p_1 \geq 5$), so this is impossible. $\square$

Lemma 1. The modular inverse $(10^d)^{-1} \bmod p_2$ can be computed via Fermat’s little theorem as $(10^d)^{p_2 - 2} \bmod p_2$, or via the extended Euclidean algorithm.

Proof. By Fermat’s little theorem, $a^{p_2 - 1} \equiv 1 \pmod{p_2}$ for $\gcd(a, p_2) = 1$. Hence $a^{-1} \equiv a^{p_2 - 2} \pmod{p_2}$. $\square$

Editorial

For consecutive primes p1, p2 with 5 <= p1 <= 1000003, find S(p1,p2): smallest positive integer ending in p1 and divisible by p2. Sum all S values.

Pseudocode

    primes = sieve_primes(1100000) // slightly above 1000003
    total = 0
    For each i in range where primes[i] >= 5 and primes[i+1] <= 1000003:
        p1 = primes[i]
        p2 = primes[i+1]
        d = number_of_digits(p1)
        pow10 = 10^d
        inv = modular_inverse(pow10, p2) // via extended GCD or Fermat
        k = (-p1 * inv) mod p2
        S = p1 + k * pow10
        total += S
    Return total

Complexity Analysis

• Time: $O(N / \ln N \cdot \log N)$ where $N \approx 10^6$. There are $\pi(10^6) \approx 78{,}498$ consecutive pairs, and each modular inverse costs $O(\log p_2)$ via the extended Euclidean algorithm.
• Space: $O(N)$ for the prime sieve.

Answer

#include <bits/stdc++.h>
using namespace std;

long long power_mod(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (__int128)result * base % mod;
        base = (__int128)base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    const int LIMIT = 1100000; // need primes a bit above 1000003
    vector<bool> is_prime(LIMIT, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < LIMIT; i++)
        if (is_prime[i])
            for (int j = i * i; j < LIMIT; j += i)
                is_prime[j] = false;

    vector<int> primes;
    for (int i = 2; i < LIMIT; i++)
        if (is_prime[i])
            primes.push_back(i);

    long long total = 0;

    for (int i = 0; i + 1 < (int)primes.size(); i++) {
        int p1 = primes[i];
        int p2 = primes[i + 1];
        if (p1 < 5) continue;
        if (p1 >= 1000003) break;

        // Number of digits of p1
        long long pow10 = 1;
        int temp = p1;
        while (temp > 0) {
            pow10 *= 10;
            temp /= 10;
        }

        // k = (-p1 * modinv(pow10, p2)) mod p2
        long long inv = power_mod(pow10, p2 - 2, p2);
        long long k = (long long)(-(long long)p1 % p2 + p2) % p2 * inv % p2;

        long long S = p1 + k * pow10;
        total += S;
    }

    cout << total << endl;
    return 0;
}

"""
Problem 134: Prime Pair Connection

For consecutive primes p1, p2 with 5 <= p1 <= 1000003, find S(p1,p2):
smallest positive integer ending in p1 and divisible by p2.
Sum all S values.
"""

def sieve(limit):
    is_prime = [True] * limit
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, limit, i):
                is_prime[j] = False
    return [i for i in range(2, limit) if is_prime[i]]

primes = sieve(1100000)

total = 0
s_values = []

for i in range(len(primes) - 1):
    p1 = primes[i]
    p2 = primes[i + 1]
    if p1 < 5:
        continue
    if p1 >= 1000003:
        break

    # Number of digits
    pow10 = 10 ** len(str(p1))

    # k = (-p1 * modinv(pow10, p2)) mod p2
    inv = pow(pow10, p2 - 2, p2)
    k = (-p1 * inv) % p2

    S = p1 + k * pow10
    total += S

    if i < 100:  # store first few for visualization
        s_values.append((p1, p2, S))

print(total)