Project Euler Problem 51

Solution

Answer: 121313

1. Mathematical analysis

We want the smallest prime that belongs to an eight-prime family formed by replacing some subset of digits with the same digit.

For example:

*3 gives six primes:

$$13,23,43,53,73,83$$

56**3 gives seven primes:

$$56003,56113,56333,56443,56663,56773,56993$$

We seek the first prime that generates 8 primes out of the 10 replacements.

Key observation 1: We only replace equal digits

Suppose we replace positions independently. Then the search explodes combinatorially.

But notice the problem statement says:

replacing part of the number with the same digit

So if we choose positions $i_1, i_2, \dots$, they must all be replaced by one common digit $d\in{0,\dots,9}$.

A natural strategy:

Generate primes.
For each prime, choose subsets of digit positions.
Replace those positions simultaneously with digits $0$–$9$.
Count how many outcomes are prime.
Stop at the first family of size 8.

Key observation 2: The replaced positions should contain the same original digit

Suppose we replace positions containing different digits.

Example:

12345, replace positions (1,3).

The family becomes:

$$10305,11315,\dots$$

But this rarely preserves structure and duplicates work.

Instead, we only consider masks over positions already containing the same digit. For a prime like 56003, we would consider replacing the two 0s.

This dramatically reduces the search space and captures the intended families.

Key observation 3: Divisibility by 3 restriction

This is the subtle mathematical trick.

Suppose we replace $k$ digits by $d$.

The digit sum changes linearly:

$$S(d)=S_0+k d$$

If $k \not\equiv 0 \pmod 3$, then as $d$ runs from 0 to 9:

$$S(d)\pmod 3$$

cycles through all residues. Therefore at least 3 values become divisible by 3.

But we need 8 primes, meaning at most 2 composites.

So:

$$k \equiv 0 \pmod 3$$

is necessary.

Thus the number of replaced digits should usually be:

$$3,6,\dots$$

This massively prunes the search.

Algorithm

For each prime $p$:

Convert to string.
Group indices by digit (0–9).
For each digit group:

consider subsets of size divisible by 3.

Replace those positions by digits 0..9.
Skip leading-zero results.
Count primes in the family.
If count = 8, return the smallest prime in that family.

Because we scan primes in increasing order, the first valid prime found is automatically the answer.

2. Python implementation

from itertools import combinations
from math import isqrt

def sieve(limit):
    """Return boolean prime table and list of primes."""
    is_prime = [True] * limit
    is_prime[0] = is_prime[1] = False

    for p in range(2, isqrt(limit) + 1):
        if is_prime[p]:
            step = p
            start = p * p
            is_prime[start:limit:step] = [False] * (
                (limit - start - 1) // step + 1
            )

    primes = [i for i, flag in enumerate(is_prime) if flag]
    return is_prime, primes

def find_smallest_prime_in_family(target_family_size=8):
    # Large enough upper bound for Problem 51
    LIMIT = 1_000_000

    is_prime, primes = sieve(LIMIT)

    for p in primes:
        if p < 10:
            continue

        s = str(p)
        n = len(s)

        # Group positions by digit
        digit_positions = {}
        for i, ch in enumerate(s):
            digit_positions.setdefault(ch, []).append(i)

        # Try replacement masks
        for digit, positions in digit_positions.items():

            # Replace counts divisible by 3
            for r in range(1, len(positions) + 1):
                if r % 3 != 0:
                    continue

                for mask in combinations(positions, r):

                    family = []

                    for replacement_digit in "0123456789":
                        chars = list(s)

                        for idx in mask:
                            chars[idx] = replacement_digit

                        # No leading zero
                        if chars[0] == "0":
                            continue

                        candidate = int("".join(chars))

                        if is_prime[candidate]:
                            family.append(candidate)

                    if len(family) == target_family_size:
                        return min(family)

    return None

answer = find_smallest_prime_in_family()
print(answer)

3. Code walkthrough

Prime generation

is_prime, primes = sieve(LIMIT)

We build a fast primality lookup table using the Sieve of Eratosthenes.

This lets us test primality in:

$$O(1)$$

time.

Loop through primes

for p in primes:

We search in increasing order.

Therefore the first successful result is automatically the smallest required prime.

Group repeated digits

For prime 56003:

digit_positions

becomes:

{
    '5': [0],
    '6': [1],
    '0': [2, 3],
    '3': [4]
}

We only replace subsets of repeated digits.

Restrict to masks divisible by 3

if r % 3 != 0:
    continue

This uses the divisibility-by-3 insight.

Without this optimization, too many replacements would automatically produce many composite numbers.

Generate the family

For each replacement digit:

for replacement_digit in "0123456789":

we replace every selected position simultaneously.

Example:

For 56**3:

d=0 → 56003
d=1 → 56113
d=2 → 56223
etc.

We count only primes.

Verify the sample

For 56003, replacing the two middle zeros gives exactly:

$$56003,56113,56333,56443,56663,56773,56993$$

which is a family of 7 primes, matching the problem statement.

Running the full search returns:

4. Final verification

Check plausibility:

It is prime ✔
Replacing the repeated digits produces 8 prime values ✔
It is larger than the 7-prime example 56003 ✔
It is the smallest because we searched primes in increasing order ✔

Answer: 121313