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 [1]:

    
def prime_factors(n): # from eratosthenes
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        
        d = d + 1
        if d * d > n:
            if n > 1:
                factors.append(n)
            break
            
    return factors

def primes_less_than_n(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
    return [2] + [i for i in xrange(3,n,2) if sieve[i]]

max_num_digits = 6
all_primes = primes_less_than_n((10**max_num_digits+1)-1)
max_p = all_primes[-1]
all_primes = set(all_primes)
print len(all_primes)

def is_prime(n):
    if n <= max_p:
        return n in all_primes
    
    return len(prime_factors(n)) == 1



In [2]:

    
truncatable = []
for p in all_primes:
    s = str(p)
    if len(s) == 1:
        continue
        
    is_trunc = True
    for i in range(1,len(s)):
        if not is_prime(int(s[:i])) or not is_prime(int(s[-i:])):
          is_trunc = False
          break
    if is_trunc:
        truncatable.append(p)
        print p
        
print sum(truncatable)