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
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.
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 SolutionRuns < 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: ",sUse this link to get the Project Euler 51 Solution Python 2.7 source.
AnswerSlowly 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.
- 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.