## Project Euler 51: Find the smallest prime which, by replacing part of the number with the same digit, is part of an eight prime value set

#### Project Euler 51 Problem Description

Project Euler 51: By replacing the 1^{st} digit of *57, it turns out that six of the possible values: 157, 257, 457, 557, 757, and 857, are all prime.

By replacing the 3^{rd} and 4^{th} digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes, 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.

#### Analysis

**REVISED**

We induced that for an eight prime value family we were looking for a 6-digit prime number with 3 repeated digits. You can’t have 2 or 4 repeating digits because at least one of the 8 versions will be divisible by 3. There are only 68,906 6-digit prime numbers to consider, but with some thought we could eliminate most of them. Here’s the process we used:

1. We need look at only those primes that have exactly 3 repeating digits.

2. The last (least significant) digit can’t be the repeating digit, because replacing it would allow composite numbers (Thanks, Rabino.)

3. Lastly, since we are checking for an eight prime value family, we need only those primes that have their repeating digit 0, 1 or 2; this reduced the set to only 1,305 primes.

Now we can iterate through the primes and report the first one that had eight prime versions.

#### Project Euler 51 Solution

Runs < 0.250 seconds in Python 2.7.Use this link to get the Project Euler 51 Solution Python 2.7 source.

#### Afterthoughts

- The file, primes51.txt, lists the 1305 prime candidates followed by the repeating digit and was generated independently. Before using a sieve to generate the primes we used this file. It is listed here for information only.

*Project Euler 51 Solution last updated*

Thanks, yes that is my mistake. Don’t know how I missed that. Just looking at it too close I think

I either have an issue with my prime generator, misunderstand the question or I think the solution given is wrong (which i’m sure its not given the number of people who solved it)

The example I’ll post here is for a 7 prime value family.

Using the Regex: “.***.” and a replacement # of 1 I get the below family of 7 prime numbers that

11113, 11117, 11119,

41113, 41117, 71119, 81119

The above example here would imply that the example given in the question is not the smallest.

I actually get a 5 digit number set for the family of 8 primes.

Can someone please tell me where I am wrong with this example?

I think you may have missed the same digit replacement rule. Your example would read: By replacing the 1st and 5th digits of *111* with the same digit…

You have to replace the wild cards (‘*’) with the same digit. The ‘111’ is the constant part.

This is a very difficult problem to understand.

Just want to reiterate that this “solution” gives the correct answer to the problem but for the wrong reasons as shown by Thibault’s post.

You are looking for primes with exactly 3 equal digits. But couldn’t you in theory have a number with 4 eqal digits, where only three of them are replaced? For example, you wouldn’t find e.g. 100003 (assuming it’s a prime, I haven’t checked), where digit 3-5 are repeaters, if neither 101113 nor 102223 are primes.

Or am I missing something?

yes, it’s just lucky the program give the right answer.

You can’t have 2 or 4 repeating digits because at least one of the 8 versions will be divisible by 3 making it composite. So, you’ll never ever need to look at any prime with 4 repeating digits because they will never make an 8-prime family.

There are two points here:

– It is true that you can’t have a family with mask xx**xx or x****x ; only mask ***xxx (and its permutations) will work.

– But a fixed digit can be equal to the repeated digits, giving one number in the family with more than 3 repeated digits.

It is in fact the case of the first 9-prime family with a mask of 38x0x2x1, when the lowest prime of its family is 38000201.

Thanks for clarifying Mike!

“We induced that for an eight prime value family we were looking for a 6-digit prime number with 3 repeated digits.”

How did you arrive at that? I have worked that out to be true by brute force programming but would like to know how that could have been established before writing my program.

“You can’t have 2 or 4 repeating digits because at least one of the 8 versions will be divisible by 3”

Again, how is that established please?

Playing a major part of the induction to search 6-digit primes was the problem’s constraint of finding the smallest prime. More digits would yield a bigger number and an increased search population.

Was it a lucky guess? Not really. It was a motive justified by intuition. Which, as practice has shown, is right more often than not.

BTW, you can rule out fewer than 6-digit primes from information garnered in the problem statement.

“You can’t have 2 or 4 repeating digits because at least one of the 8 versions will be divisible by 3″

Again, how is that established please?

There is an old rule that states:

Add up all the digits in the number and if that sum is divisible by 3 then so is the number.

Having 2 or 4 repeating digits in an 8 6-digit family will always lead to a composite number in at least one of the members.

We’ll leave proof as an exercise.

why do we need to check for only those primes having 0,1 or 2 as repeating digit?

Good question! I should have been more clear. {0,1,2} was an arbitrary decision; it could have been any three unique digits such as {3,7,9}. The intent was to reduce duplicate searches during the replacement. Replacing {0,1,2} would eventually have replacing {7,8,9} as the same candidate. So by limiting the set to some three arbitrary digits would eliminate the redundancy.

This program will still work by ignoring the {1,2,3} constraint – it would just take longer.

Knowing that the least significant digit cant be part of the replacement, you can filter from the list the numbers that only have 3 repeating digits including the last one. The initial list could start in 5817 elements

Cheers

I’m going to update this solution with your clever insight. Thanks for commenting.