Problem 111: Primes with Runs

Mathematical Development

Theorem 1 (Repdigit composite bound). A repdigit number $\underbrace{dd \cdots d}_{n}$ with $n \geq 2$ and $1 \leq d \leq 9$ is composite.

Proof. Write $\underbrace{dd \cdots d}_{n} = d \cdot R_n$ where $R_n = \frac{10^n - 1}{9}$ is the repunit of length $n$. For $n \geq 2$, we have $R_n \geq R_2 = 11$, so the factorization $d \cdot R_n$ is nontrivial (both factors exceed 1). $\blacksquare$

Corollary 1. For all $n \geq 2$ and digits $d \in \{0, 1, \ldots, 9\}$, $M(n, d) \leq n - 1$.

Proof. If $d = 0$, an $n$-digit number cannot have all $n$ digits equal to 0 (it would be zero). If $d \geq 1$, the $n$-digit number $\underbrace{dd \cdots d}_n$ is composite by Theorem 1. In both cases, no $n$-digit prime consists entirely of a single repeated digit. $\blacksquare$

Theorem 2 (Candidate enumeration). For fixed $n$, $d$, and $k$ (the number of positions holding digit $d$), the number of candidate $n$-digit numbers with exactly $k$ positions equal to $d$ is

where $E(n, k, d)$ counts candidates with a leading zero.

Proof. Select which $n - k$ of the $n$ positions hold a digit other than $d$: there are $\binom{n}{n-k}$ ways. Each such position admits 9 choices from $\{0, 1, \ldots, 9\} \setminus \{d\}$, yielding $\binom{n}{n-k} \cdot 9^{n-k}$ candidates in total. However, any candidate with leading digit 0 does not represent a valid $n$-digit number and must be excluded. $\blacksquare$

Lemma 1 (Deterministic primality for 10-digit numbers). The Miller—Rabin primality test with witness set $W = \{2, 3, 5, 7, 11, 13\}$ is deterministic for all integers $n < 3.2 \times 10^{13}$. In particular, it correctly classifies every 10-digit number.

Proof. Jaeschke (1993) proved that no strong pseudoprime to all bases in $W$ exists below $3.2 \times 10^{13}$. Since every 10-digit number satisfies $n < 10^{10} < 3.2 \times 10^{13}$, the test is infallible in this range. $\blacksquare$

Theorem 3 (Greedy descent correctness). The algorithm that sets $k = n - 1$ and decreases $k$ by 1, at each level exhaustively enumerating all $n$-digit candidates with exactly $k$ copies of digit $d$ and testing each for primality, correctly determines $M(n, d)$: the first level $k$ at which a prime is found equals $M(n, d)$.

Proof. By definition, $M(n, d) = \max\{k : \exists \text{ an } n\text{-digit prime with exactly } k \text{ copies of } d\}$. Corollary 1 gives $M(n, d) \leq n - 1$. The algorithm starts at this upper bound and descends. At each level $k$, it performs an exhaustive search over all valid candidates (Theorem 2) and applies a correct primality test (Lemma 1). Hence, the first $k$ yielding at least one prime is the maximum such $k$, which is $M(n, d)$ by definition. $\blacksquare$

Editorial

We first generate the primes required by the search, then enumerate the admissible combinations and retain only the values that satisfy the final test.

Pseudocode

    total = 0
    For d from 0 to 9:
        for k = 9 downto 1:
            primes_found = []
            for each subset P of {0, 1, ..., 9} with |P| = 10 - k:
                For each each assignment of digits from {0,...,9}\{d} to positions in P:
                    construct N with digit d at all positions not in P
                    If leading_digit(N) != 0 and N >= 10^9 and IsPrime(N) then
                        primes_found.append(N)
            If primes_found is not empty then
                total += sum(primes_found)
                break
    Return total

    Miller-Rabin with witnesses {2, 3, 5, 7, 11, 13}
    write n - 1 = 2^r * d with d odd
    For each a in {2, 3, 5, 7, 11, 13}:
        x = a^d mod n
        If x == 1 or x == n - 1 then continue
        For i from 1 to r - 1:
            x = x^2 mod n
            If x == n - 1 then stop this loop
        else: return false
    Return true

Complexity Analysis

• Time. For each digit $d \in \{0, \ldots, 9\}$, the greedy descent starts at $k = 9$ (i.e., $n - k = 1$ free position). At level $k = 9$, the candidate count is $\binom{10}{1} \cdot 9 = 90$. At level $k = 8$, it is $\binom{10}{2} \cdot 9^2 = 3645$. In practice, most digits find primes at $k = 9$ or $k = 8$. Over all 10 digits, the total number of candidates tested is at most $10 \times 3645 = 36{,}450$. Each Miller—Rabin test costs $O(\log^2 n)$ with 6 witnesses, where $n < 10^{10}$. Since $\log_2(10^{10}) \approx 33$, each test performs a bounded number of modular exponentiations. Total: $O(1)$ (constant with respect to the problem parameters).
• Space. $O(1)$ beyond a small list of primes per $(d, k)$ pair.

Answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;

bool miller_rabin(ll n, ll a) {
    if (n % a == 0) return n == a;
    ll d = n - 1;
    int r = 0;
    while (d % 2 == 0) { d /= 2; r++; }
    ll x = 1, base = a % n, dd = d;
    while (dd > 0) {
        if (dd & 1) x = (lll)x * base % n;
        base = (lll)base * base % n;
        dd >>= 1;
    }
    if (x == 1 || x == n - 1) return true;
    for (int i = 0; i < r - 1; i++) {
        x = (lll)x * x % n;
        if (x == n - 1) return true;
    }
    return false;
}

bool is_prime(ll n) {
    if (n < 2) return false;
    for (ll a : {2, 3, 5, 7, 11, 13})
        if (!miller_rabin(n, a)) return false;
    return true;
}

int main() {
    const int n = 10;
    ll total = 0;
    for (int d = 0; d <= 9; d++) {
        for (int k = n - 1; k >= 1; k--) {
            int free = n - k;
            vector<int> combo(free);
            ll sum_p = 0;
            function<void(int, int)> gen_combos = [&](int start, int idx) {
                if (idx == free) {
                    function<void(int, ll)> gen_digits = [&](int i, ll num) {
                        if (i == n) {
                            if (num >= 1000000000LL && is_prime(num))
                                sum_p += num;
                            return;
                        }
                        bool is_free = false;
                        for (int j = 0; j < free; j++)
                            if (combo[j] == i) { is_free = true; break; }
                        if (!is_free) {
                            gen_digits(i + 1, num * 10 + d);
                        } else {
                            for (int dd = 0; dd <= 9; dd++) {
                                if (dd == d) continue;
                                gen_digits(i + 1, num * 10 + dd);
                            }
                        }
                    };
                    gen_digits(0, 0);
                    return;
                }
                for (int i = start; i < n; i++) {
                    combo[idx] = i;
                    gen_combos(i + 1, idx + 1);
                }
            };
            gen_combos(0, 0);
            if (sum_p > 0) { total += sum_p; break; }
        }
    }
    cout << total << endl;
    return 0;
}

from itertools import combinations


def is_prime(n):
    """Deterministic Miller-Rabin for n < 3.2 * 10^13 (Jaeschke 1993)."""
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for a in (2, 3, 5, 7, 11, 13):
        if a >= n:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True


def solve():
    n = 10
    total = 0
    for d in range(10):
        for k in range(n - 1, 0, -1):
            free = n - k
            sum_primes = 0
            for positions in combinations(range(n), free):
                pos_set = set(positions)

                def generate(idx, num):
                    nonlocal sum_primes
                    if idx == n:
                        if num >= 10 ** (n - 1) and is_prime(num):
                            sum_primes += num
                        return
                    if idx in pos_set:
                        for dig in range(10):
                            if dig != d:
                                generate(idx + 1, num * 10 + dig)
                    else:
                        generate(idx + 1, num * 10 + d)

                generate(0, 0)
            if sum_primes > 0:
                total += sum_primes
                break
    print(total)


solve()