# Problem 37

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.

``````

In :

def primes_upto(n):
"""
Generator for primes up to n.
For primes under 'n', just use n-1.
"""
if n < 2:
return
marked =  * (n+1);
value = 3
yield 2
while value <= n:
if marked[value] == 0:
yield value
i = value
while i <= n:
marked[i] = 1
i += value
value += 2

def is_leftright_truncatable(n, P):
if n not in P:
return False
s = str(n)[1:]
if len(s) == 0:
return True
return is_leftright_truncatable(int(s), P)

def is_rightleft_truncatable(n, P):
if n not in P:
return False
s = str(n)[:-1]
if len(s) == 0:
return True
return is_rightleft_truncatable(int(s), P)

def is_truncatable_prime(n, P):
if n not in P:
return False
if n < 10:
return False
return is_leftright_truncatable(n,P) and is_rightleft_truncatable(n,P)

def truncatable_primes_upto(limit):
P = set(primes_upto(limit))
for i in P:
if is_truncatable_prime(i, P):
yield i

``````
``````

In :

X = set(truncatable_primes_upto(1000000))
print(len(X))

``````
``````

11

``````
``````

In :

print(X)

``````
``````

{3137, 37, 739397, 73, 797, 53, 373, 23, 3797, 313, 317}

``````
``````

In :

print(sum(X))

``````
``````

748317

``````
``````

In [ ]:

``````