Project Euler 111: Search for 10-digit primes containing the maximum number of repeated digits.

So in Problem 111 of Project Euler we are back at dealing with prime numbers. And rather large ones of them. But before going into details, here is the problem description

Considering 4-digit primes containing repeated digits it is clear that they cannot all be the same: 1111 is divisible by 11, 2222 is divisible by 22, and so on. But there are nine 4-digit primes containing three ones:

1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111

We shall say that M(nd) represents the maximum number of repeated digits for an n-digit prime where d is the repeated digit, N(nd) represents the number of such primes, and S(nd) represents the sum of these primes.

So M(4, 1) = 3 is the maximum number of repeated digits for a 4-digit prime where one is the repeated digit, there are N(4, 1) = 9 such primes, and the sum of these primes is S(4, 1) = 22275. It turns out that for d = 0, it is only possible to have M(4, 0) = 2 repeated digits, but there are N(4, 0) = 13 such cases.

In the same way we obtain the following results for 4-digit primes.

Digit, d M(4, d) N(4, d) S(4, d)
0 2 13 67061
1 3 9 22275
2 3 1 2221
3 3 12 46214
4 3 2 8888
5 3 1 5557
6 3 1 6661
7 3 9 57863
8 3 1 8887
9 3 7 48073

For d = 0 to 9, the sum of all S(4, d) is 273700.

Find the sum of all S(10, d).

I rather quickly realized that there must be two solution approaches to this problem. Either we generate all the primes in the range and start finding the right ones. Or we can generate numbers with repeated digits and check if they are primes.

I started out with the first approach, by trying to generate primes up to 10.000.000.000, but I ran into problems with my sieve as we have to index more than can be stored in an integer. So either I could rewrite the sieve or I could look into the other approach.

Generating numbers

The way I went around with it, was to create an array of length 10 to store the digits in and then combine those. Once we have generated a number there are 2 things we need to check. The first one is that if the number starts with a zero, it is invalid as a candidate. The other is to check whether it is a prime number. For the latter part we can use the Rabin-Miller probabilistic method we developed in Problem 58. This method can be made deterministic using the right array of checks.

So to check a number we can use the following piece of code

private long CheckNumber() {
    if (number[0] == 0) return 0;
    long n = 0;

    for(int i = 0; i < number.Length; i++){
        n = n*10 + number[i];
    }

    return IsProbablePrime(n, new int[] { 2, 3, 5, 7, 11 }) ? n : 0;
}

I did build a solution myself, but I could never get it to be pretty, so when I found a recursive solution in the solution pages of Project Euler, I decided that I wanted to go with that instead. So the code here is not my original code. So this piece of recursive code returns the sum of primes which with basedigit given as input, starting position being the position of the non-repeating digit that we investigate and level being the number of non-repeating digits.

private long Recurse(int basedigit, int startpos, int level, bool fill = false) {
    if (level     long res = 0;
    if (fill) {
        for (int pos = 0; pos < number.Length; pos++) {
            number[pos] = basedigit;
        }
    }
    for (int pos = startpos; pos < number.Length; pos++) {
        for (int val = 0; val < 10; val++) {
            number[pos] = val;
            res += Recurse(basedigit, pos + 1, level - 1);
            number[pos] = basedigit;
        }
    }
    return res;
}

The code can be a little intimidating at first, at least that is how I feel when I see recursive code like that, but really, it just generates all the possibilities with the given number of non-repeating digits and a given basenumber.

Searching through the candidates

The last thing we need now is to generate all the possible candidates using the recursing function. We should be aware of when we are generating numbers is that if we can find just one number with 9 repeating digits there is no need to search for numbers with 8 repeating digits of that kind. So we might be able to limit our search in that regard.

Therefore the code looks as

long result = 0;
for (int d = 0; d < 10; d++){
    for (int i = 1; i < number.Length; i++) { long sum = Recurse(d, 0, i, true); if (sum > 0) {
            result += sum;
            break;
        }
    }
}

This code runs in 12.2ms and gives us the result

S(10,d) = 612407567715

Wrapping up

This can be solved rather quickly when generating the candidates in a clever way. You can find the complete source code here.

Posted by Kristian

7 comments

Hello, my code for this runs in 78 ms. Is slower because of method isPrime which runs in o(n/2) time which is slow.

#include <iostream>
#include <ctime>
#include <cmath>
#include <vector>


using namespace std;
typedef unsigned long long Long;
const int PRIME_LIMIT = 100000;
int primes[40000];
int totalPrimes;
Long number[10][2];
Long numberToCheck;
void primeSieve();
void makeNumber();
bool isPrime();

int main()
{


    time_t start = clock();

    primeSieve();

    int i,j;
    bool found;
    Long sum = 0;
    vector<int> twoDiffernet; //numbers which have got 2 different digits
    twoDiffernet.push_back(0);

    for(i = 9; i >= 0; i--)             //initialize value of each digit
        number[i][1] = pow(10, (9 - i));

    for(i = 1; i<10; i++)     //for each number
    {

        found = false;      //no such prime found

        for(j = 0; j<10; j++)    //initialize number
            number[j][0] = i;

        for(j = 0; j<10; j++)     //roll through each digit
        {

            for(int k = 0; k<10; k++)   //exactly once
            {
                number[j][0] = k;
                if(isPrime())
                {
                    sum += numberToCheck;
                    found = true;
                }
            }

            number[j][0] = i;

        }

        if(found == false)
            twoDiffernet.push_back(i);

    }
     

    //ok now we have secured all the numbers with 1 different digit

    for(i = 0; i<twoDiffernet.size(); i++)
    {


        for(j = 0; j<10; j++)    //initialize number
            number[j][0] = twoDiffernet[i];

        for(j = 0; j<10; j++)     //roll through each digit
        {

            for(int k = 0; k<10; k++)   //exactly once
            {
                number[j][0] = k;

                for(int x = j+1; x<10; x++)
                {
                    for(int y = 0; y<10; y++)
                    {
                        number[x][0] = y;

                        if(isPrime())
                        {
                            sum += numberToCheck;
                            found = true;
                        }
                    }
                    number[x][0] = twoDiffernet[i];
                }
            }

            number[j][0] = twoDiffernet[i];

        }

    }


    cout<<sum<<endl;
    cout<<"Program last:\t"<<(clock()- start)<<endl;

}


void primeSieve()
{

    int i,j;
    bool values[PRIME_LIMIT];

    for(i = 0; i<PRIME_LIMIT; i++)
        values[i] = true;


    for(i = 2; i<PRIME_LIMIT; i++)
        if(values[i])
        {
            for(j = i+i; j<PRIME_LIMIT; j+=i)
                values[j] = false;

            primes[totalPrimes++] = i;
        }
}

void makeNumber()
{

    int i;
    numberToCheck = 0;
    for(i = 0; i<10; i++)
        numberToCheck += number[i][0] * number[i][1];

}


bool isPrime()
{

    if(number[0][0] == 0)    //if first digit is 0
        return false;

    int i;
    makeNumber();

    if(numberToCheck % 2 == 0)    //if is even
        return false;

    const int SQRT = sqrt(numberToCheck);
    for(i = 3; i<=SQRT; i+=2)
        if(numberToCheck % i == 0)
            return false;

    return true;



}

Is there a chance that you publish the value S(10,d) for some d’s? The only difference between my solution and yours is that mine ends with 5, not with 2, and that’s driving me crazy.

Sorry for the long reply time, you have probably solved it already. But here are a few results for your debugging

S(10,0) = 38000000042
S(10,1) = 12882626601
S(10,2) = 97447914665

I hope that these helps you. Otherwise let me know.

Jean-Marie Hachey

Table 1
4-digit primes containing the maximum number of repeated digits.
[re: Project Euler 111]

http://img11.hostingpics.net/pics/144535pe111tableone.jpg

Table 2
10-digit primes containing the maximum number of repeated digits 0, 1 and 2.
[re: Project Euler 111]

http://img11.hostingpics.net/pics/355959pe111tabletwo.jpg

___

Sources:

1) Project Euler 111
Kristian’s algorithm
http://www.mathblog.dk/files/euler/Problem111.cs

2) Microsoft Visual C# 2010 Express
(Reference added : System.Numerics)

3) Microsoft Office Excel (2007)

Sandu Ursu

Hi, Kristian!

I use Mathematica, and I have implemented the following function which gives me S[n,d]:

S[n_,d_]:=Module[{k=1,S=0},
While[S==0,
NN=Permutations[Flatten[{#,0Range[n-k]+d}]]&/@Subsets[Complement[Range[0,9],{d}],{k}];
S=Select[FromDigits/@Flatten[NN,1],PrimeQ[#]&&#>10^(n-1)&]//Total;
k++
];
S]

The total sum is then just:

S[10,#]&/@Range[0,9]//Total

and it yields instantly: 594629790343.

However, my final result is wrong, and I have no clue why…

Here are my S[10,d]s:

S[10,0] 38000000042
S[10,1] 12882626601
S[10,2] 97447914665
S[10,3] 23234122821
S[10,4] 4444444447
S[10,5] 5555555557
S[10,6] 6666666661
S[10,7] 59950904793
S[10,8] 267992164834
S[10,9] 78455389922

Please let me know where my results are wrong.

Hi Sandu, No consolation but I get exactly the same result as you in my Ruby program. It runs in 1s and the sums are all OK, except for d=8. The correct answer finds 32 such primes, but my code (and yours I suppose) finds only 30. I don’t why two are missed and I don’t know yet which ones they are.

As I was solving this problem I had a similar problem as peter and Sandu Ursu, they weren’t considering the posibilities of other repeated digits. S[10,8] is the only instance where the other two digits are the same, IE, 8888888383 is a valid solution.

Leave a Reply