# 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 idea : 
#
#  1. While eleven truncatable primes have not been found :
#        Test new primes to see if they are truncatable.
#
#  2. Find the sum of the eleven truncatable primes which have
#  been found.
#
#  To implement this in a fast way, we use a slightly modified
#  version of Eratosthenes' sieve, which finds new primes in
#  blocks of suitable size.
#
#----------------------------------------------------------------#



#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#
#%%%%%%%%%%%%%%%%%%%%%%   The Solution     %%%%%%%%%%%%%%%%%%%%%%#
#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#

# Solve the problem. 
def problem_37() :

    # In the beginning we don't know any truncatable prime
    count = 0
    truncatable_primes = []
    primes_list = []
    
    # Keep looking for truncatable primes till all 11 have been found.
    while (count < 11):
        old_length = len(primes_list)
        
        # Find the primes in the next block of 10000 numbers.
        primes_list = new_primes(primes_list, 10000) 
        new_length = len(primes_list)

        # For each new prime, check if it is truncatable. The
        # single-digit primes are not considered truncatable.
        i = old_length 
        if i < 8 :
            i = 11
            
        while i < new_length : 
            if primes_list[i] : # True if and only if i is prime. 
                # We reuse primes_list in this function instead of
                # computing it again.
                if is_truncatable(i, primes_list) : 
                    truncatable_primes.append(i)
                    count = count + 1
            i = i + 1
    
    print "The truncatable primes are : " + str(truncatable_primes)
    # Return the sum of all the truncatable primes.
    return sum(truncatable_primes)
                         
#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#
#%%%%%%%%%%%%%%%%%%   Helper Functions     %%%%%%%%%%%%%%%%%%%%%%%#
#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#


# Accepts a (possibly empty) list of Boolean (True/False) values
# which has the following property :
#
#   For each index i of the list, list[i] is True if and only if i
#   is a prime number.

# Returns a list which is longer by "count", and has the same
# property as the argument list. Uses Eratosthenes' sieve to
# compute this extension.
def new_primes(primes_list, count) :

    # "Every number is prime until proved composite."
    extension = [True] * count
    
    # list.extend(new_list) is the "big brother" of
    # list.append(new_element).
    primes_list.extend(extension)

    # 0 and 1 are special cases.
    primes_list[0] = False
    primes_list[1] = False
    
    new_length = len(primes_list)
    
    # It is enough to sift using divisors up till the square root.
    limit = int(new_length**(1.0/2)) + 1
    
    # The "sieve" : 
    for i in range(2, limit) :
        if primes_list[i] :
            for j in range(2*i, new_length, i) :
                primes_list[j] = False
                        
    return primes_list

# Returns a list of all the non-empty truncations of the string
# given as the argument.
def all_truncations(string):
        truncations = []
        length = len(string)

        for i in range(1, length):
            truncations.append(string[i:])
            truncations.append(string[:i])
        return truncations

# Accepts a number and a Boolean "list of primes" which contains
# information about all primes up to this number. Checks whether
# the number is truncatable or not.
def is_truncatable(number, primes_list) :
    # We assume that the number is truncatable, till we find
    # evidence against this.
    truncatable = True

    truncations = all_truncations(str(number))

    for string in truncations :
        num = int(string)

        # If this "sub" number is not prime, then the original
        # number (argument) is not truncatable.
        if not primes_list[num] :
            truncatable = False

    return truncatable
    

                
# For testing
print "The sum of all the truncatable primes is : " + str(problem_37())