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

It looked obvious from the example that the minimum prime value for an 8 prime family had to have at least 6 digits. For that size of prime it would take at least 3 digits to have to be replaced. The last digit couldn’t be part of the replacement because that would make it non-prime.

So we took all 68,906 6-digit primes and reduced it to 11,066 by keeping only those primes that had 3 or more repeating digits. We also remembered which digit was repeating so that replacing it would be easy.

All that was left was to iterate through the primes and report the first one that followed the instructions outlined above.

Solution

Runs < 1 second in Perl.

open IN, "<primes51.txt" or die "Cannot open file: $!";
%primes = map {chomp; split /,/} <IN>;
for $p (sort keys %primes) {
  $dd = $primes{$p}; $c=1; $i=0;
  for $d ( grep {$_!=$dd} (0..9) ) {
    last if $i-$c>2;
    $xx=$p; $xx=~s/$dd/$d/g;
    $c++ if exists $primes{$xx};
    $i++;
    next if $c<8;
    print "Answer to PE50 = $p";exit;
  }
}

Comments

Example of what file ‘primes51.txt’ looks like:
104999,9
105211,1
105557,5
106121,1