Truncatable Primes

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.

The first step is to build a list of truncatable prime numbers. A brute force method isn’t going to be efficient for this, so a good approach is to build a list of primes that have other primes in all of their potential truncations.

First, note that any truncatable prime with more than one digit has to have the first and last digits as 3 or 7. The reason for this is as follows:

– A prime number above 10 can never end with the digits 0, 2, 4, 5, 6, or 8 since it would be divisible by 2 or 5.
– Similarly, if we truncate the number from the right, the remaining number cannot begin with the digits 1 or 9 because at some point we would have a number that ends with 1 or 9, which would not be a prime number.
– And, a truncatable prime number cannot begin or end with the digit 5 because the number would be divisible by 5 at some point.
– So a truncatable prime has to begin and end with 3 or 7.

Keeping this in mind, we work to generate all such primes. Truncatable primes can be two, three, four, five, six or seven digits long. Generating all two-digit primes that start and end with 3 or 7, we get 4 primes: [37, 73, 37, 73].

When we go to three digits, we combine these two-digit primes with [3, 7], prepend and append, then remove all non-primes. This gives us [373, 337, 773, 739, 797, 733, 379, 971, 937, 977, 757, 577].

Repeating this process for four, five, six and seven digits, gives us the following truncatable primes (excluding 2, 3, 5, and 7): [37, 73, 313, 373, 733, 317, 797, 3797, 739397, 3797, 3733797, 37397, 73].

The sum of these primes is 748317.

More Answers: