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.
Number the digits of a truncatable prime as \(d_1 d_2 \ldots d_k\). Because \(d_1 d_2 \ldots d_i\) is prime for all \(i \in \{2, \ldots, k\}\), \(d_i \in \{1, 3, 7, 9\}\) for all such \(i\). Also, \(d_1 \in \{2, 3, 5, 7\}\) and \(d_k \in \{3, 7\}\), because the first and last digits must themselves be prime. From these principles it's just a matter of searching through all candidates until we find eleven truncatable primes.
from itertools import count, product
from sympy import isprime
# Splitting this part to a separate function so as to not stretch the page
def is_trunc_prime(s):
if not isprime(int(s)):
return False
for i in range(1, len(s) - 1):
n1, n2 = int(s[i:]), int(s[:-i])
if not isprime(n1) or not isprime(n2):
return False
return True
def p37():
found, res = 0, 0
for k in count(0):
for head in "2357":
for body in product("1379", repeat=k):
for tail in "37":
s = head + ''.join(body) + tail
if is_trunc_prime(s):
found += 1
res += int(s)
if found == 11:
return res