Project Euler 51: Find the smallest prime which, by changing the same part of the number, can form eight different primes

Project Euler 51: Find the smallest prime which, by changing the same part of the number, can form eight different primes

Written by on 9 July 2011

Topics: Project Euler

When I worked on this problem I realised that I value two things about code – speed and simplicity. I always try to obtain both but in this case I had to sacrifice the simplicity in order to gain speed as we shall see. But before we dive into the code lets look at Problem 51 which is the problem description for the first problem on the second page of Project Euler. It reads

By replacing the 1st digit of *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

This problem can be solved in multiple ways.  You could run your way through all primes and check if each one is part of a family or you could do a bit of analysis on the problem to narrow down the problem you have to solve by code. I have chosen the latter.

Problem Analysis

First of all we are looking for an 8 member family. And since we are looking for the smallest member of the family our repeated digits has to be 0, 1 or 2. Otherwise we wont be able to make an eight member family.

Besides saying something about the size of the repeated digit we can also say something about the number of repeated digits in the family. A number can be divided by 3 if the digit sum is is divisible by 3.  If we calculate the digit sum mod 3 of the repeated digits we get the following results with the number of repeated digits

ResultNumber of repeated digits
12345
0441044
133033
233033

If the number we have has 1 repeated digit then the result n%3 will be 0 4 times, namly for 0, 3, 6 and 9. It will be 1 a total of 3 times and 2 a total number of 3 times.

What this tells us is, that no matter what digit we are repeating we will get at most 7 primes. The exception being if we have 3 repeating digit (or a multiplum of three repeating digits). Another rule that has to be fulfilled is that the non-repeating digits have a digit sum mod 3 different from 0.

What more can be said is that a prime number always ends in 1,3, 7 or 9 for primes larger than 10. This excludes the last digit from being a repeated digit.

So now we know a bit more about the kind of prime we are looking for. I assume that the prime will be 5 or 6 digits. It must have 3 digit being 0,1 or 2 excluding the last digit of the number.

So lets make some code.

Pattern Generation

Now that we have some knowledge of the problem it is time to find a solution strategy. The solution strategy here is to generate all patterns of repeating and non repeating digits and then loop. Since I assume that we are looking for a 5-6 digit number we need to loop the non repeating digits over 11-999 and we need to loop the repeating digits over 0-2.

Since the last digit is fixed using the binomial coefficient tells me that for a 5 digit number I can pick one out of 4 in 4 different ways, and for the 6 digit case I can pick 2 out of 5 in 10 different ways. I have chosen the manual approach to generating patterns.

private int[][] get5digitPatterns() {
    int[][] retVal = new int[4][];

    retVal[0] = new int[]{1,0,0,0,1};
    retVal[1] = new int[]{0,1,0,0,1};
    retVal[2] = new int[]{0,0,1,0,1};
    retVal[3] = new int[]{0,0,0,1,1};

    return retVal;
}

private int[][] get6digitPatterns() {
    int[][] retVal = new int[10][];

    retVal[0] = new int[] { 1, 1, 0, 0, 0, 1 };
    retVal[1] = new int[] { 1, 0, 1, 0, 0, 1 };
    retVal[2] = new int[] { 1, 0, 0, 1, 0, 1 };
    retVal[3] = new int[] { 1, 0, 0, 0, 1, 1 };
    retVal[4] = new int[] { 0, 1, 1, 0, 0, 1 };
    retVal[5] = new int[] { 0, 1, 0, 1, 0, 1 };
    retVal[6] = new int[] { 0, 1, 0, 0, 1, 1 };
    retVal[7] = new int[] { 0, 0, 1, 1, 0, 1 };
    retVal[8] = new int[] { 0, 0, 1, 0, 1, 1 };
    retVal[9] = new int[] { 0, 0, 0, 1, 1, 1 };

    return retVal;
}

Having a 0 in the pattern means we have a repeated digit, and 1 means a nonrepeating digit.

Candidate generation

Second thing we need is methods to fill the pattern and to generate the final number. I know two tasks could be written as one method, but I want to split them up. It is all pretty simple, and the c# implementation looks like

private int[] fillPattern(int[] pattern, int number) {
    int[] filledPattern = new int[pattern.Length];
    int temp = number;

    for (int i = filledPattern.Length - 1; 0 <= i; i--) {
        if (pattern[i] == 1) {
            filledPattern[i] = temp % 10;
            temp /= 10;
        } else {
            filledPattern[i] = -1;
        }
    }
    return filledPattern;
}

private int generateNumber(int repNumber, int[] filledPattern) {
    int temp = 0;
    for (int i = 0; i < filledPattern.Length; i++) {
        temp = temp * 10;
        temp += (filledPattern[i] == -1) ?
            repNumber : filledPattern[i];
    }
    return temp;
}

So the first one fills a pattern with the non repeating digits, putting -1 on spot where we will place repeating digits. The second method creates a number based on the filled pattern and a value for the repeated digit.

Before going to the main algorithm and before going to try to make some sense out of it, I need to present one more method called familysize which takes a patter and a repeating digit and returns the number of primes in the family.

private int familySize(int repeatingNumber, int[] pattern) {
    int familySize = 1;

    for (int i = repeatingNumber + 1; i < 10; i++) {
        if (isPrime(generateNumber(i, pattern))) familySize++;
    }

    return familySize;
}

As you can see this method checks to see if a number is a prime number. Here I use a modified trial division from problem 7 which you can see in the available source code. With all the helper functions in place we are ready to write the main loop.

Main Algorithm

I think I will skip all the chit chat and present the algorithm right away

int[][] fiveDigitPattern = get5digitPatterns();
int[][] sixDigitPattern = get6digitPatterns();
int result = int.MaxValue;

for (int i = 11; i < 1000; i += 2) {

    //Only 1,3,7,9 are valid endings
    if (i % 5 == 0) continue;

    int[][] patterns = (i < 100) ?
        fiveDigitPattern : sixDigitPattern;

    for(int j = 0; j         for(int k = 0; k <= 2; k++){

            //Don't generate candidates with leading zero
            if (patterns[j][0] == 0 && k == 0) continue;

            int[] pattern = fillPattern(patterns[j], i);
            int candidate = generateNumber(k, pattern);

            if (candidate < result && isPrime(candidate)) {
                if (familySize(k, pattern) == 8 )
                    result = candidate;
                break;
            }
        }
    }
}

The method of generating candidates and see if they are primes and fulfil the requirements rather than generating all primes and finding the right one gives us the challenge that the candidates aren’t ordered. So we are not generating the smallest number first. Therefore line 23 checks if the new candidate is smaller than the currently best result. When I realised I could add that I cut a nice chuck out of the solution time.

Wrapping up

It has been a rather long piece of code this time with a lot of methods. As you can see I valued speed over simplicity for this problem. The result of running the solution for Problem 51 in C# is the following

First prime in the eight prime family is 121313
Solution took 3 ms

That means the solution is faster than generating all primes up to one million using the sieve method. So I must say I am pretty satisfied with the solution.
You can find the complete source code here.

What do you think of the solution? Is it too complicated? Is it understandable?

Can it be done differently? certainly. Can it be done faster? Not a whole lot I guess.

Last but not least I would like to thank Eschipul who provided the image for me under the creative commons license. I am of course resharing the alteration under the same license.

19 Comments For This Post I'd Love to Hear Yours!

  1. SuprDewd says:

    I went with sieving and replacing digits (running time 1 sec).
    Your solution is understandable and not too complicated (given a pretty complicated problem). Only thing I would have changed is the type of the pattern array. It seems more natural for me to use an array of booleans instead of integers. Less space (only a few bytes in this case) and faster equality checking. But this solution probably wont gain a lot from that.

    Great solution overall.

  2. Kristian says:

    You are absolutely right, I should probably have used bool arrays instead. But for some reason I used integer arrays and was too lazy to change it.

    And as you mention it probably does not make a whole lot of difference.

  3. David says:

    What medium do you use to write the program?

  4. Kristian says:

    I am not sure what you mean by medium. If you mean the editor I use to write the program in? In that case, I use Visual Studio Express as IDE.

    /Kristian

  5. Nitin says:

    very nice solution !! But can you explain a bit more how did you come to the conclusion that there would be 2 or 3 repeating digits. I couldn’t get the table above. And moreover why these prime numbers will be of 5 or 6 digits ?

    Thanks!!

  6. Kristian says:

    Hi Nitin

    Thanks for the kind words. Yes I will try to explain a bit more.

    The table can be a bit tricky to read, so I have added the explanation If the number we have 1 repeated digit then the result n%3 will be 0 4 times, namly for 0, 3, 6 and 9. It will be 1 a total of 3 times and 2 a total number of 3 times.

    This means if we have 1 repeating digit and the digit sum of the non repeating digits is 0 we will add 0 4 times. Which means that 4 of those numbers will be divisible with 3. Therefore 4 of those numbers wont be prime and we can’t have an 8-member family then. The same goes with all other numbers except 3, 6 and 9.

    My guess for a 5-6 digit number was nothing more than a guess.

  7. Sam says:

    hi!, i did mine a little different, problly not very best code, but anyways my question is this. My answer was 101149. I checked all of its permutations, and all eight of them were primes too.

  8. russ says:

    Of all the problems I’ve solved on PE (in almost perfect sequential order, “almost” thanks to this problem) this was definitely the hardest. I don’t know why, and the most annoying. In fact I still haven’t solved it but thought I’d try and pick up something from here and translate to Python. I wonder if anyone else had a PE problem that they just for some reason couldn’t crack but knew it was within they’re reach.

  9. Kristian says:

    I was stuck on problem 88 for a good while and I knew I almost had the right idea. So yes I do know what it feels like.

  10. Corky says:

    This problem was frustrating to me due to the wording. I came to your blog looking for why I was wrong, as I’m a frequent lurker when I want to improve execution time (after I solve a problem, of course).

    I thought that 120383 was a valid answer. Even after re-reading the problem text, I wasn’t grasping “Find the smallest prime which… is part of an eight prime value family” – just the smallest prime that generates the family.

    /facepalm

  11. Kristian says:

    Don’t know what to say to you, but glad that you figured it out. I have been in those situations myself, where you figure the problem, but answer the wrong thing anyway.

  12. Chum says:

    This sentence is nonsensical (copy/paste error?), and makes the whole chart-explanation section difficult to understand:

    “That means that if we no matter what the digit sum of the non repeating digit we will get at most 7 primes except if we use 3 repeating digits[…]”

    (Btw, love the blog. You have helped me think about many PE problems in important cool ways, and I have learned much about number-theory from you — thanks!)

  13. Kristian says:

    Thanks for the comment. I have tried to update the paragraph to be more readable. Though I have a hard time making a good formulation out of it.

  14. Shobhit says:

    This one took me quite a while to figure out because I was trying to solve the wrong problem.
    I thought you could replace only two positions of a digit e.g. 121313 can result only in 222313, 323313, 424313 etc. I actually did solve that but it was much more complex than the original problem and needless to say, I was not getting the right answer.
    I came to your site looking for hints but unlike other solutions, it was difficult for me to follow what you suggested. Part of the reason was my misunderstanding about the problem.
    Eventually I understood the problem and solved it very quickly. I attacked it in a semi brute force way. Generated a list of primes, replaced the recurring digit and checked for primeness. Return if number of primes is 8.

  15. hussein says:

    I want to ask about the assumption to consider all of non-repeating 0 and check if the number is divisible by 3 by adding only the repeated digits.
    Didnt get that.

  16. Kristian says:

    Hi. I guess you are refering to the analysis part?

    What I have done is that I have taken a number of repeated digits (x-axis) and then I have tried with all values 0 to 9 and checked the result modulo 3. So the result of that operation is between 0 and 2.

    The data shows that for 1 repeating digit the result will be zero a total number of 4 times (0,3,6,9), 1 a total number of 3 times (1, 4, 7) and 2 a total number of 3 times (2,5,8).

    Based on that I can concluce that the repeating digit has to be three, otherwise I will never be able to make 8 different primes out of it, since too many of the candidates will be divisble by three no matter what the rest of the number is.

  17. Rasmus says:

    As a intermediate programmer studying my second year of computer science, I must say that this write-up was outstanding; I felt as if this really took it to the next level. This is just the thing which got me into programming. Thanks a whole lot!

    I will, without any doubts, check out more content on this website.

  18. Adhyyan says:

    As a 14 year old programmer I found this extremely helpful and without this I wouldn’t be able to write my own algorithm. Even though i have trouble understanding line 13 of your main algorithm.. I don’t understand why there was a need for using the nested for loop(the one looping from k =0 to 2) because you are using the same numbers again and this would increase the computation time by a factor of 3.

    According me to, you should check whether the original number is prime is the familySize() function rather than looping from 0 to 2 as it is doing the same thing over and over. So the repNumber is FamilySize() starts from 0 all the way to 9.

    Thank You for this excellent post.

  19. Vishal says:

    Getting beautiful insights from you blog, thank you !!
    but still one thing that haunts me is why you used only to check whether digit is divisible by 3, why not any other number ?

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.