Detailed mathematical approach

Problem Summary

For each digit \(d \in \{0,1,\dots,9\}\), let \(M(10,d)\) be the largest number of times that \(d\) can appear in a 10-digit prime, and let \(S(10,d)\) be the sum of all 10-digit primes that attain this maximum repetition count. The goal is to compute

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

The important point is that the optimization is digit-specific. For each fixed digit \(d\), we are not looking for all primes with many repeated digits in general; we are looking for primes with as many copies of that one chosen digit as possible.

Mathematical Approach

The implementations solve the problem by turning "maximum repetition" into the equivalent question "how few positions must be changed before a prime appears?" That reformulation matches the combinatorial structure of the search exactly.

Minimal replacement count instead of maximal repetition

Fix a digit \(d\). Let \(r_d\) be the smallest integer \(r \ge 1\) for which there exists a 10-digit prime with exactly \(r\) digits different from \(d\). Then a prime found at that first successful level contains \(10-r_d\) copies of \(d\), so

$M(10,d)=10-r_d.$

If we write \(\mathcal{P}(d,r)\) for the set of 10-digit primes with exactly \(r\) non-\(d\) digits, then the desired sum for digit \(d\) is

$S(10,d)=\sum_{p\in \mathcal{P}(d,r_d)} p.$

This is why the search can stop immediately once primes are found: any larger value of \(r\) would only decrease the number of repeated \(d\)'s, so it can never improve \(M(10,d)\).

The correct state space: choose positions, then choose digits

For a fixed pair \((d,r)\), start from the word \(dddddddddd\). Choose a set \(P\subseteq\{0,1,\dots,9\}\) of \(r\) positions that will be changed, and then assign to each chosen position a digit from \(\{0,\dots,9\}\setminus\{d\}\). Because changed positions are forced to receive digits different from \(d\), every valid assignment has exactly \(r\) non-\(d\) digits and is generated exactly once.

Before any decimal or primality filters, the raw search space at level \(r\) is therefore

$\binom{10}{r} 9^r.$

This factorization into combinations of positions and assignments of digits is the central combinatorial object in the solution, and all three implementations mirror it directly.

Decimal constraints that remove entire families of candidates

Not every assignment can represent a 10-digit prime. Two elementary facts eliminate many cases before primality testing.

First, the leading digit cannot be zero. If \(d=0\) and the first position is not among the changed positions, then the candidate is not a 10-digit integer at all.

Second, every prime greater than \(5\) ends in \(1\), \(3\), \(7\), or \(9\). So if the last position is unchanged and \(d\notin\{1,3,7,9\}\), that entire pattern is impossible. If the last position is changed, only digits in \(\{1,3,7,9\}\setminus\{d\}\) need to be tried there.

The C++ implementation applies the ending-digit rule explicitly before calling the prime test. The same mathematics is still present in the Python and Java versions, even when the filter is enforced implicitly by the prime test.

Worked example: why the digit \(0\) cannot succeed with one replacement

This is a good example of the difference between a structural argument and blind brute force. Suppose only one position were allowed to differ from \(0\).

If the first digit is not changed, the number begins with \(0\), so it is not a valid 10-digit number. If the first digit is the unique changed position, then the final digit is still \(0\), so the number is divisible by \(10\) and cannot be prime. Therefore one replacement is impossible for \(d=0\).

So we know immediately that

$r_0\ge 2,\qquad M(10,0)\le 8.$

The search still confirms this computationally, but the conclusion comes from place-value arithmetic alone.

Why the first nonempty level is exactly the one we need

Suppose the search reaches a value \(r\) and finds at least one prime. Then every one of those primes has exactly \(10-r\) copies of \(d\). On the other hand, the search has already proved that no prime exists for any smaller replacement count \(1,2,\dots,r-1\). Hence no 10-digit prime can contain more than \(10-r\) copies of \(d\), and the current level is automatically optimal.

That observation is the key invariant of the whole approach: descending repetition counts are equivalent to ascending replacement counts, and the first successful level already determines both \(M(10,d)\) and \(S(10,d)\).

How the Code Works

Outer search over digits and replacement counts

The C++, Python, and Java implementations loop over \(d=0,1,\dots,9\). For each digit they try \(r=1,2,\dots,10\), where \(r\) is the number of positions that are not equal to \(d\). That is the computational version of searching for \(r_d\), the minimal replacement count.

Candidate generation with exact repetition control

At a fixed \((d,r)\), the implementation fills a 10-slot digit array with \(d\), enumerates all \(\binom{10}{r}\) choices of changed positions, and then enumerates all digit assignments on those positions that avoid the value \(d\). Because the repeated digit is restored after each branch, every completed array still represents a number with exactly \(10-r\) copies of \(d\).

Leading-zero cases are rejected immediately. The C++ implementation also skips numbers whose final digit is even or equal to \(5\), because such numbers cannot be prime unless the whole number is \(2\) or \(5\), which is impossible here.

Primality testing and accumulation

Once a candidate passes the decimal filters, it is converted to an integer and tested for primality. The C++ implementation uses modular multiplication, modular exponentiation, and a deterministic Miller-Rabin test that is valid for 64-bit inputs in this range. The Python and Java implementations rely on mature high-level primality routines. All primes found at the first successful level for digit \(d\) are added together, and the final answer is the sum of those ten digit-specific totals.

Complexity Analysis

If \(r_d\) is the first successful replacement count for digit \(d\), then the work for that digit is bounded by

$O\!\left(\sum_{r=1}^{r_d}\binom{10}{r}9^r \cdot T_{\mathrm{prime}}\right),$

where \(T_{\mathrm{prime}}\) is the cost of one primality test on a 10-digit integer. This expression is problem-adaptive: it measures exactly the amount of search the implementations perform before the optimal repetition count is certified.

Memory usage is \(O(10)\) for the current digit array plus small temporary storage for the primes found at the first successful level. Since the target length is fixed at 10 digits and the search stops as soon as the optimum is reached for each digit, the practical runtime is very small.

Footnotes and References

1. Problem page: Project Euler 111 - Primes with runs
2. Prime numbers: Wikipedia - Prime number
3. Miller-Rabin primality test: Wikipedia - Miller-Rabin primality test
4. Binomial coefficients: Wikipedia - Binomial coefficient
5. Divisibility rules: Wikipedia - Divisibility rule
6. Repdigits: Wikipedia - Repdigit