// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (9 votes, average: 5.00 out of 5)
Loading ... Loading ...

Project Euler Solutions

Project Euler 51 Solution

Project Euler 51 Solution

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


Problem Description

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.
from Euler import prime_sieve, is_prime
import string
 
def eight_prime_family(prime, rd):
    c=0
    for digit in '0123456789':
        n = int(string.replace(prime, rd, digit))
        if (n>100000 and is_prime(n)):
            c=c+1
    return c==8
 
for prime in prime_sieve(1000000):
    if (prime>100000):
        s = str(prime)
        last_digit = s[5:6]
        if (s.count('0')==3 and eight_prime_family(s,'0') \
         or s.count('1')==3 and last_digit != '1' and eight_prime_family(s,'1') \
         or s.count('2')==3 and eight_prime_family(s,'2')):
             print "Project Euler 51 Solution: ",s
Use this link to get the Project Euler 51 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|121313|

Comments

  • 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

Discussion

12 Responses to “Project Euler 51 Solution”

  1. 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

    Posted by Rabino | December 7, 2010, 12:42 PM
  2. why 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 PM
    • 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.

      Posted by Mike | July 12, 2011, 7:01 PM
  3. “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 AM
    • 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.

      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 AM
  4. Thanks for clarifying Mike!

    Posted by schlongers | March 23, 2012, 12:58 AM
  5. 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?

    Posted by Diana | June 4, 2012, 1:04 PM
    • yes, it’s just lucky the program give the right answer.

      Posted by LN | November 2, 2012, 4:43 PM
    • 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.

      Posted by Mike | November 3, 2012, 12:00 AM
      • 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.

        Posted by Thibault | April 27, 2013, 1:17 AM

Post a comment