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

The quantity $M(10,d)$ is defined by a maximum repetition count, so the search should start from the top. For a fixed digit $d$, we first ask whether a 10-digit prime exists with nine copies of $d$. If not, we allow two non-$d$ positions, then three, and so on. The first repetition count that produces any prime is automatically the maximal one, so all primes found at that level contribute to $S(10,d)$.

The implementation follows that definition directly. It chooses which positions are allowed to differ from $d$, fills those positions with digits other than $d$, rejects candidates with a leading zero, and runs a deterministic Miller—Rabin test on the resulting 10-digit number. Summing the primes found at the first successful level for each digit $d = 0,1,\ldots,9$ gives the required total.

Pseudocode

Set the overall sum to zero.

For each repeated digit d from 0 through 9:
    Try repetition counts from 9 downward until a prime appears.
    For the current repetition count, choose the positions that are allowed to differ from d.
    Fill those free positions with digits other than d to form every candidate number with exactly that many copies of d.
    Discard any candidate with a leading zero, and test every remaining candidate for primality.
    If at least one prime is found at this level, add their sum to the overall total and stop descending for this digit.

Return the overall sum.

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()