- Dreamshire - http://blog.dreamshire.com -

Project Euler 51

Posted By Mike On May 27, 2009 @ 1:48 AM In Project Euler Solutions,Solutions 51-100

Problem Description

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.

Solution

Runs < 1 second in Python.

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 "Answer to PE51: ",s

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.


Article printed from Dreamshire: http://blog.dreamshire.com

URL to article: http://blog.dreamshire.com/2009/05/27/project-euler-problem-51-solution/

Copyright © 2009 Dreamshire. All rights reserved.