[C/C++] Project Euler #51 - Prime Digit Replacements

Project Euler Problem #51 is the first problem that doesn’t have a difficulty rating of 5%.

Compared to problems #1 to #50, this one is a bit more challenging, with a difficulty rating set at 15%.

---

The problem gives a number like 56xx3, where the x represents blank digits. By replacing each x with digits from 0 to 9, we want to find out how many of the resulting numbers are prime.

For example, by replacing the xs in 56xx3, we can generate the following 10 numbers:

56003, 56113, 56223, 56333, 56443, 56553, 56663, 56773, 56883, 56993

Among these, 7 are prime numbers. In this case, 56003 (the smallest in the group) is the smallest number that yields 7 primes in this way.

The goal of the problem is to find the smallest prime that, when certain digits are replaced with the same digit, yields 8 prime numbers.

---

The challenging part is figuring out how to apply the problem logic; once that’s done, a computer can solve it in a short time.

I primarily used recursion to solve this. Recursion seems to be a convenient method when generating all possible combinations.

I also assumed the number of digits wouldn’t need to be very large.

Since the smallest number that gives 7 primes is a 5-digit number, I started from 5-digit numbers and increased the number of digits gradually. To speed up the process, I only considered numbers that end in 1, 3, 7, or 9.

I used three variables: digit, mask, and count, each playing a role in solving the problem.
• digit is the number of digits. For example, if we use 6 digits, digit would be 6.
• mask represents the blank positions. The number of blanks can go from 1 to digit - 1 (since the last digit must be one of 1, 3, 7, or 9).
• Once the blanks and positions are determined, the count variable is used to measure how many of the resulting numbers are primes. When this count reaches 8, we’ve found our answer.

---

prime digit replacements

Below is the code I wrote.
Please note: the code is for reference only.

//------------------------------------------------
//    Project Euler #51 - Prime Digit Replacements
//        - by Aubrey Choi
//        - created at 2015-03-31
//------------------------------------------------
#include <stdio.h>
#include <memory.h>
#include "isprime.h"

#define    TARGET    8

int FindDigit(int digit, int holes, int mask, int s);
int GetPrimeFamily(int c, int digit, int n, int mask);

int main()
{
    for( int digit = 5 ; digit < 7; digit++ )
    {
        for( int holes = 1 ; holes < digit ; holes++ )
        {
            int v = FindDigit(digit, holes, 0, 1);
            if( v ) { printf("Ans = %d\n", v); return 0; }
        }
    }
}

int FindDigit(int digit, int holes, int mask, int s)
{
    if( holes == 0 )
    {
        const int s[4] = { 1, 3, 7, 9 };
        for( int i = 0 ; i < 4 ; i++ )
        {
            int v = GetPrimeFamily( 1, digit, s[i], mask );
            if( v ) return v;
        }
        return 0;
    }

    //    Make holes
    for( int i = s ; i <= digit-holes ; i++ )
    {
        int v = FindDigit(digit, holes-1, mask | (1<<i), i+1);
        if( v ) return v;
    }
    return 0;
}

int GetPrimeFamily(int c, int digit, int n, int mask)
{
    if( c == digit )
    {
        int s = 10, m = 0, count = 0;
        for( int i = 1 ; i < digit ; i++, s *= 10 ) if( (mask>>i)&1 ) m += s;
        if( !(mask>>(digit-1)) && n*10/s == 0 ) return 0;
        int start = (mask>>(digit-1));
        for( int i = start ; i < 10 ; i++ )
            if( isPrime(n+i*m) ) count++;
        if( count < TARGET ) return 0;
        printf("digit = %d, n = %d, mask = %X, count = %d\n", digit, n, mask, count);
        for( int i = start ; i < 10 ; i++ )
            if( isPrime(n+i*m) ) printf("%d ", n+i*m);
        putchar('\n');
        for( int i = start ; i < 10 ; i++ )
            if( isPrime(n+i*m) ) return n+i*m;
    }

    if( (mask>>c)&1 ) return GetPrimeFamily(c+1, digit, n, mask);
    int t = 1;
    for( int i = 0 ; i < c ; i++, t *= 10 );
    for( int k = 0 ; k < 10*t ; k += t )
    {
        int v = GetPrimeFamily(c+1, digit, n+k, mask);
        if( v ) return v;
    }
    return 0;
}

 

Find the smallest prime number which, by replacing part of the number (some digits in the same positions) with the same digit, yields 8 prime numbers in the resulting family.

key algorithms

 

---

1. Digit Masking for Position Selection

int FindDigit(int digit, int holes, int mask, int s)

• Recursively generates all combinations of digit positions (using bitmasking) to place “holes” (i.e., replaceable digits).
• Ensures that:
• Only holes number of positions are masked.
• The last digit is never masked (since a valid prime can’t end in even digits or 5).
• Uses bit manipulation: mask | (1 << i) marks the i-th position as a hole.

➡️ Purpose:
Finds all valid digit positions to be replaced using bitmasking.

---

2. Prime Family Generator

int GetPrimeFamily(int c, int digit, int n, int mask)

• Recursively builds numbers digit by digit.
• When the number is fully built (c == digit), it replaces the masked positions with digits 0 through 9 and counts how many resulting numbers are prime.
• If at least 8 primes are found in this family, it returns the smallest such prime.

➡️ Purpose:
Generates the family of numbers by filling in digits in the masked positions, and checks if the family contains at least 8 primes.

---

3. Filtering Valid Digits

const int s[4] = {1, 3, 7, 9};

• Optimization: Only considers numbers ending in 1, 3, 7, or 9 (since primes cannot end in even digits or 5, except for the number 2 or 5 themselves).

➡️ Purpose:
Improves performance by ignoring impossible candidates.

---

4. Recursive Combination Builder

for( int k = 0 ; k < 10*t ; k += t )

• Builds all possible values for digits not masked.
• For example, if position 1 is not masked, it loops through all values for that digit.

➡️ Purpose:
Builds all number combinations not affected by the mask using place value arithmetic.

---

📦 Supporting Structures
• digit: Number of digits to consider (starting from 5).
• holes: Number of digits to be replaced.
• mask: Bitmask to define the replaceable digit positions.
• isPrime(n): Primality check function (assumed to be defined in "isprime.h").

---

🧩 Overall Flow
1. Try 5-digit numbers (then 6-digit, etc.).
2. For each digit count:
• Choose combinations of positions to replace (holes) via bitmasking.
• For each such mask, generate all base numbers.
• Replace the masked digits with 0–9 and count primes in the family.
3. If a family with 8 primes is found, return the smallest.