Loading...
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 1st 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 3rd and 4th 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.
Thanks, yes that is my mistake. Don’t know how I missed that. Just looking at it too close I think
Posted by Calum | December 18, 2016, 7:55 PMI 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?
Posted by Calum | December 15, 2016, 7:33 PMI 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.
Posted by Mike Molony | December 18, 2016, 7:47 PMJust want to reiterate that this “solution” gives the correct answer to the problem but for the wrong reasons as shown by Thibault’s post.
Posted by JC | July 18, 2016, 6:41 PMYou 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?
Posted by Diana | June 4, 2012, 1:04 PMyes, it’s just lucky the program give the right answer.
Posted by LN | November 2, 2012, 4:43 PMYou 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.
Posted by Mike | November 3, 2012, 12:00 AMThere 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.
Posted by Thibault | April 27, 2013, 1:17 AMThanks for clarifying Mike!
Posted by schlongers | March 23, 2012, 12:58 AM“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?
Posted by schlongers | March 22, 2012, 4:28 AMPlaying 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.
Posted by Mike | March 22, 2012, 11:50 AM“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.
Posted by Mike | March 22, 2012, 11:59 AMwhy do we need to check for only those primes having 0,1 or 2 as repeating digit?
Posted by xx | July 6, 2011, 2:03 PMGood 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.
Posted by Mike | July 12, 2011, 7:01 PMKnowing 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
Posted by Rabino | December 7, 2010, 12:42 PMI’m going to update this solution with your clever insight. Thanks for commenting.
Posted by Mike | December 7, 2010, 5:03 PM