Problem 111: Primes with Runs
View on Project EulerProject Euler Problem 111 Solution
EulerSolve provides an optimized solution for Project Euler Problem 111, Primes with Runs, with C++, Python, Java, and a step-by-step mathematical explanation.
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\)....
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
- Problem page: Project Euler 111 - Primes with runs
- Prime numbers: Wikipedia - Prime number
- Miller-Rabin primality test: Wikipedia - Miller-Rabin primality test
- Binomial coefficients: Wikipedia - Binomial coefficient
- Divisibility rules: Wikipedia - Divisibility rule
- Repdigits: Wikipedia - Repdigit
Problem 111 source code
C++
#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
namespace {
using u64 = std::uint64_t;
using u128 = unsigned __int128;
struct Options {
int digits = 10;
bool run_checkpoints = true;
};
bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
if (arg.rfind(prefix, 0U) != 0U) {
return false;
}
const std::string tail = arg.substr(prefix.size());
if (tail.empty()) {
return false;
}
int parsed = 0;
for (char c : tail) {
if (c < '0' || c > '9') {
return false;
}
parsed = parsed * 10 + static_cast<int>(c - '0');
}
value = parsed;
return true;
}
bool parse_arguments(int argc, char** argv, Options& options) {
for (int i = 1; i < argc; ++i) {
const std::string arg(argv[i]);
if (arg == "--skip-checkpoints") {
options.run_checkpoints = false;
continue;
}
if (parse_int_after_prefix(arg, "--digits=", options.digits)) {
continue;
}
std::cerr << "Unknown argument: " << arg << '\n';
return false;
}
return options.digits >= 2;
}
u64 mul_mod(u64 a, u64 b, u64 mod) {
return static_cast<u64>((static_cast<u128>(a) * static_cast<u128>(b)) % mod);
}
u64 pow_mod(u64 base, u64 exp, u64 mod) {
u64 result = 1 % mod;
base %= mod;
while (exp > 0) {
if ((exp & 1ULL) != 0ULL) {
result = mul_mod(result, base, mod);
}
base = mul_mod(base, base, mod);
exp >>= 1ULL;
}
return result;
}
bool is_prime(u64 n) {
if (n < 2) {
return false;
}
for (u64 p : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) {
if (n == p) {
return true;
}
if (n % p == 0ULL) {
return false;
}
}
u64 d = n - 1;
int s = 0;
while ((d & 1ULL) == 0ULL) {
d >>= 1ULL;
++s;
}
for (u64 a : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL}) {
if (a % n == 0ULL) {
continue;
}
u64 x = pow_mod(a, d, n);
if (x == 1ULL || x == n - 1) {
continue;
}
bool witness = true;
for (int r = 1; r < s; ++r) {
x = mul_mod(x, x, n);
if (x == n - 1) {
witness = false;
break;
}
}
if (witness) {
return false;
}
}
return true;
}
void choose_positions(const int n,
const int k,
const int start,
std::vector<int>& current,
std::vector<std::vector<int>>& all) {
if (static_cast<int>(current.size()) == k) {
all.push_back(current);
return;
}
for (int i = start; i <= n - (k - static_cast<int>(current.size())); ++i) {
current.push_back(i);
choose_positions(n, k, i + 1, current, all);
current.pop_back();
}
}
void assign_replacements(const int idx,
const std::vector<int>& positions,
const int repeated_digit,
std::vector<int>& digits,
std::vector<u64>& primes) {
if (idx == static_cast<int>(positions.size())) {
if (digits[0] == 0) {
return;
}
const int last = digits.back();
if ((last % 2) == 0 || last == 5) {
return;
}
u64 value = 0;
for (int d : digits) {
value = value * 10ULL + static_cast<u64>(d);
}
if (is_prime(value)) {
primes.push_back(value);
}
return;
}
for (int d = 0; d <= 9; ++d) {
if (d == repeated_digit) {
continue;
}
digits[static_cast<std::size_t>(positions[static_cast<std::size_t>(idx)])] = d;
assign_replacements(idx + 1, positions, repeated_digit, digits, primes);
}
}
u64 sum_for_digit(const int n, const int repeated_digit) {
for (int replacements = 1; replacements <= n; ++replacements) {
std::vector<std::vector<int>> position_sets;
std::vector<int> current;
choose_positions(n, replacements, 0, current, position_sets);
std::vector<u64> primes;
std::vector<int> digits(static_cast<std::size_t>(n), repeated_digit);
for (const std::vector<int>& positions : position_sets) {
assign_replacements(0, positions, repeated_digit, digits, primes);
for (int pos : positions) {
digits[static_cast<std::size_t>(pos)] = repeated_digit;
}
}
if (!primes.empty()) {
std::sort(primes.begin(), primes.end());
primes.erase(std::unique(primes.begin(), primes.end()), primes.end());
u64 sum = 0;
for (u64 p : primes) {
sum += p;
}
return sum;
}
}
return 0;
}
u64 solve(const int digits) {
u64 total = 0;
for (int d = 0; d <= 9; ++d) {
total += sum_for_digit(digits, d);
}
return total;
}
bool run_checkpoints() {
if (solve(4) != 273700ULL) {
std::cerr << "Checkpoint failed for n=4" << '\n';
return false;
}
return true;
}
} // namespace
int main(int argc, char** argv) {
Options options;
if (!parse_arguments(argc, argv, options)) {
return 1;
}
if (options.run_checkpoints && !run_checkpoints()) {
return 2;
}
std::cout << solve(options.digits) << '\n';
return 0;
}
Python
# Problem 111: Primes with runs
# Sum of all 10-digit primes with maximum repeated digits.
from sympy import isprime
from itertools import combinations
def solve():
n = 10
total = 0
for d in range(10):
for replacements in range(1, n + 1):
primes = []
positions = list(combinations(range(n), replacements))
for pos in positions:
digits = [d] * n
def fill(idx, digs):
if idx == len(pos):
if digs[0] == 0: return
val = int(''.join(map(str, digs)))
if isprime(val):
primes.append(val)
return
for r in range(10):
if r == d: continue
digs[pos[idx]] = r
fill(idx + 1, digs)
digs[pos[idx]] = d
fill(0, digits)
if primes:
total += sum(set(primes))
break
print(total)
solve()
Java
import java.math.BigInteger;
public class Euler111 {
static boolean isPrime(long n) {
if (n < 2)
return false;
if (n < 4)
return true;
if (n % 2 == 0 || n % 3 == 0)
return false;
BigInteger bi = BigInteger.valueOf(n);
return bi.isProbablePrime(30);
}
public static void main(String[] args) {
int N = 10;
long total = 0;
for (int d = 0; d <= 9; d++) {
boolean found = false;
for (int rep = 1; rep <= N && !found; rep++) {
// rep = number of positions replaced (non-d digits)
long sum = 0;
boolean any = false;
int[] pos = new int[rep];
for (int i = 0; i < rep; i++)
pos[i] = i;
// iterate over all combinations of 'rep' positions out of N
outer: while (true) {
int[] digits = new int[N];
java.util.Arrays.fill(digits, d);
// try all replacement values
int[] repl = new int[rep];
inner: while (true) {
boolean valid = true;
for (int i = 0; i < rep; i++) {
if (repl[i] == d) {
valid = false;
break;
}
digits[pos[i]] = repl[i];
}
if (valid && digits[0] != 0) {
long val = 0;
for (int i = 0; i < N; i++)
val = val * 10 + digits[i];
if (isPrime(val)) {
sum += val;
any = true;
}
}
// restore
for (int i = 0; i < rep; i++)
digits[pos[i]] = d;
// next replacement combo
int carry = rep - 1;
while (carry >= 0) {
repl[carry]++;
if (repl[carry] < 10)
break;
repl[carry] = 0;
carry--;
}
if (carry < 0)
break;
}
// next combination
int k = rep - 1;
while (k >= 0 && pos[k] == N - rep + k)
k--;
if (k < 0)
break;
pos[k]++;
for (int i = k + 1; i < rep; i++)
pos[i] = pos[i - 1] + 1;
}
if (any) {
total += sum;
found = true;
}
}
}
System.out.println(total);
}
}