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

    
def primes_upto(n):
    """
    Generator for primes up to n.
    For primes under 'n', just use n-1.
    """
    if n < 2:
        return
    marked = [0] * (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 [2]:

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



In [3]:

    
print(X)









    



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



In [4]:

    
print(sum(X))



In [ ]: