Solution

Answer: 612407567715

Let $M(n,d)$ be the maximum number of repeated digits $d$ that can occur in an $n$-digit prime.

For this problem, we need:

$$\sum_{d=0}^9 S(10,d)$$

where $S(10,d)$ is the sum of all 10-digit primes containing digit $d$ exactly $M(10,d)$ times.

Mathematical analysis

A brute-force search over all 10-digit numbers is impossible:

$$9 \times 10^9$$

numbers is far too many.

The key observation is that we are specifically searching for primes with many repeated digits. That massively reduces the search space.

Step 1 — Search by repeated digit count

For each digit $d\in{0,\dots,9}$:

Try $m=10,9,8,\dots$
Generate all 10-digit numbers containing exactly $m$ copies of digit $d$
Test primality
The first $m$ producing at least one prime is $M(10,d)$

This works because $M(10,d)$ is defined as the maximum repetition count.

Step 2 — Construct candidates efficiently

Suppose digit $d$ is repeated $m$ times.

Then:

choose the $m$ positions occupied by $d$
fill the remaining $10-m$ positions with digits different from $d$

For example, if:

$d=7$
$m=9$

then only one digit position differs from $7$.

We use:

$$\binom{10}{m}$$

choices for the repeated positions.

The remaining digits are generated with Cartesian products.

Step 3 — Leading zero restriction

A valid 10-digit number cannot begin with zero.

So we reject any candidate whose first digit is $0$.

Step 4 — Primality testing

All candidates are below:

$$10^{10}$$

For this range, deterministic Miller–Rabin with a fixed witness set is extremely fast and fully reliable.

A standard witness set for $n < 2^{64}$ is:

$${2,325,9375,28178,450775,9780504,1795265022}$$

This gives deterministic correctness for all 64-bit integers.

Python implementation

from itertools import combinations, product

# ---------------------------------------------------------
# Deterministic Miller-Rabin for 64-bit integers
# ---------------------------------------------------------
def is_prime(n):
    if n < 2:
        return False

    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

    for p in small_primes:
        if n % p == 0:
            return n == p

    # write n-1 = d * 2^s
    d = n - 1
    s = 0

    while d % 2 == 0:
        s += 1
        d //= 2

    # deterministic witnesses for 64-bit integers
    witnesses = [2, 325, 9375, 28178,
                 450775, 9780504, 1795265022]

    for a in witnesses:
        if a % n == 0:
            continue

        x = pow(a, d, n)

        if x == 1 or x == n - 1:
            continue

        for _ in range(s - 1):
            x = pow(x, 2, n)

            if x == n - 1:
                break
        else:
            return False

    return True

# ---------------------------------------------------------
# Compute S(10, d)
# ---------------------------------------------------------
def solve(n=10):
    total_sum = 0

    positions = range(n)

    for d in range(10):

        # Try largest repetition count first
        for m in range(n, 0, -1):

            current_sum = 0
            prime_count = 0

            repeated_positions_sets = combinations(positions, m)

            for repeated_positions in repeated_positions_sets:

                repeated_positions = set(repeated_positions)

                other_positions = [
                    i for i in positions
                    if i not in repeated_positions
                ]

                # Fill remaining positions with digits != d
                for digits in product(range(10),
                                      repeat=n - m):

                    number = [d] * n

                    valid = True

                    for pos, value in zip(other_positions, digits):

                        if value == d:
                            valid = False
                            break

                        number[pos] = value

                    if not valid:
                        continue

                    # no leading zero
                    if number[0] == 0:
                        continue

                    value = int("".join(map(str, number)))

                    if is_prime(value):
                        current_sum += value
                        prime_count += 1

            # first successful m is M(n,d)
            if prime_count > 0:
                print(
                    f"d={d}, M={m}, "
                    f"N={prime_count}, S={current_sum}"
                )

                total_sum += current_sum
                break

    return total_sum

answer = solve()
print("\nFinal answer =", answer)

Code walkthrough

Miller–Rabin

def is_prime(n):

Fast primality test.

We first remove small factors:

for p in small_primes:

Then write:

$$n-1 = d \cdot 2^s$$

which is required for Miller–Rabin.

The witnesses used are deterministic for all 64-bit integers.

Main search

for d in range(10):

Process each repeated digit separately.

Try repetition counts from largest downward

for m in range(n, 0, -1):

The first successful $m$ is $M(10,d)$.

Choose repeated positions

combinations(positions, m)

These are the positions occupied by digit $d$.

Fill remaining positions

product(range(10), repeat=n-m)

Generate all possible remaining digits.

We reject any occurrence of $d$ in these positions because we want exactly $m$ copies of $d$.

Build the number

number = [d] * n

Then overwrite the non-$d$ positions.

Reject leading zero

if number[0] == 0:

Ensures a true 10-digit number.

Prime test

if is_prime(value):

Accumulate the sum and count.

Verification on the sample $n=4$

The program reproduces the values from the statement:

$M(4,1)=3$
$S(4,1)=22275$
total $=273700$

which confirms correctness.

Computed values for $n=10$

The search finds:

d	M(10,d)	S(10,d)
0	8	38000000042
1	9	12882626601
2	8	97447914665
3	9	23234122821
4	9	4444444447
5	9	5555555557
6	9	6666666661
7	9	59950904793
8	8	285769942206
9	9	78455389922

Summing them gives:

$$612407567715$$

The magnitude is reasonable: there are many 10-digit primes, and the sums are on the order of $10^{10}$ each.

Answer: 612407567715

Project Euler Problem 111