Problem Description

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

Analysis

The good news is the problem tells us there’s only 11. We can just keep searching a bunch of primes until 11 meet the criteria.

With just some casual thought it occurred to us that since we are going to truncate in both directions only primes ending in 3 or 7 are valid. Also any prime with at least one digit from the set [0, 2, 4, 5, 6, 8] would make the prime invalid. Add to that pairs such as ’11′, ’33′, ’77′ or ’99′ and the possible prime numbers gets smaller.

Two problems: The two digit primes 23 and 53 would violate our filter (we found these by looking at the table of prime numbers), so we will have to mark these as exceptions. And just how big can these primes get?

One way to find out is just to get started and see what happens. This code gave us our solution set and the answer.

After seeing the results, we realized we could build a tree to ferret out the set of primes. Here’s a tree for 2, 5, and 7. We’ll leave 3 as an exercise.

2 — 3

5 — 3

   3 — 9 — 3 — 9 — 7
7 — 9 — 7

When a prime starts with 7 it can only be followed by 3 or 9. For the 9 branch only a 7 can come next and no other number would follow. A 3, 1, 7 or 9 would produce a composite number as 39, 9, 77 or 1.
The same logic follows for the 3 side.

Solution

Runs < 1 second in Perl.

use integer;
my $s = 23 + 53;  #first two that are exceptions to our pattern
open IN, "<primes2.txt";
@p = grep {!/[024568]/ && /[37]$/ && /^(3[17][^1]|7[39][^13])/ && !/99|77|33|11/} <IN>;
while ($c<11) {
  $q=shift @p;
  if (trunc($q)) {
    $c++;
    $s+=$q;
  }
}
print "Answer to PE37 = $s, $c primes found";
 
sub trunc {
 my $c = $d = shift;
 while ($d) {
  return 0 unless is_prime($d) && is_prime($c);
  $c%=10**(length($c)-1);
  $d/=10;
 }
return 1
}

Comments

Didn’t have fun with this one. Here’s the set: [23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]
Here’s the start of our regex code to sift out the 11 primes from a file of primes. It reduces the list of 78,499 primes from 2 – 1,000,000 to just 28. Not up to finishing it.

open IN, "<primes2.txt";
@p = grep {!/[024568]/ && /[37]$/ && /^(3[17][^1]|7[39][^13])/ && !/99|77|33|11/} <IN>;