Python Program Stall Out, When n > 373 and Always on line 32

Rather than testing primes individually, you can "assemble" a prime number by combining the possible first, middle and last digits.

The first digit has to be a prime because it's going to end up alone when truncating the right side.
So the first digit can only be 2, 3, 5 or 7

The last digit also has to be a prime but it will also be the last digit of a multi-digit number that must be a prime. So it can't be even and it can't be 5 (numbers ending with 5 are multiples of 5).
So the last digit can only be 3 or 7

Middle digits will eventually be the last digit of a prime number so they can't be even and they can't be 5.
So middle digits can only be 1, 3, 7 or 9.

Given this, you can "build" numbers by combining these digits and check that they are prime and truncable:

def isPrime(N):     return all(N%d for d in range(2,int(N**0.5)+1))
def isLeftTrunc(S): return all(isPrime(int(S[i:])) for i in range(len(S)))

def truncablePrimes(prefix=None):
    if not prefix:
        for p in (2,3,5,7):                    # first digits (2,3,5,7)
            yield from truncablePrimes(p*10)   # expand with suffixes
        return
    for n in (prefix+3,prefix+7):              # last digits (3,7)
        if isLeftTrunc(str(n)):                # return truncables
            yield n
    for n in (prefix+1,prefix+3,prefix+7,prefix+9): # middle digits (1,3,7,9)
        if isPrime(n):                              # valid right truncable
            yield from truncablePrimes(n*10)        # expand with suffixes

output:

print(sorted(truncablePrimes()))
# [23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397]

print(sum(truncablePrimes()))
# 748317

This runs in 0.0000003 second

From what I can tell, your code should get the correct results with enough time/computing power. The problem is that the program spends a lot of time doing unnecessary work.

For example, think about what happens when n is very large but still divisible by 3, such as 204483. Even though you quickly know it can't be prime, the program is still scanning through the other thousands of primes.

There's also a similar inefficiency in test_trun.

Another subtle slow spot is checking v not in primes. Since Python only knows primes as an unsorted list, this is slow. https://wiki.python.org/moin/TimeComplexity

As a fellow Eulerian, I can't tell you exactly how to fix it, but you are close. Good luck!

Thank you to everyone who answered, you gave me some ideas, which over the past couple of days I've implemented. I switched my for loops to while loops, which checked whether the test had already failed before proceeding. I found a bug in my prime search, where because a lack of indentation caused my n to be increased by 4 each time it wasn't prime. I also added about 15 different debugging print commands, of which most have now been commented out.

I was going to also create a binary search function that would more efficiently check whether a trun_versions[v] was in primes, but it found the answer anyway after running in the background for about 3 minutes.

I am however perplexed why the second condition for my while loop in the test_trun function doesn't require me to subtract1 from the len(trun_versions) as the indices of a list start at 0, right?

# 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.

primes = [2, 3, 5, 7, 11, 13]
trun_primes = []

# Tests whether number "n" is a trucatable prime, doesn't test whether "n" is prime itself
def test_trun(t):
    trun_versions = []
    for d in range(1, len(str(n))):
        trun_versions.append(int(str(t)[:len(str(n)) - d]))
        trun_versions.append(int(str(t)[d:]))
    # print "TRUN_VERSIONS = " + str(trun_versions)
    ttest = 0
    v = 0
    # NO CLUE why the following line does not function unless v != len(trun_versions) - 1 is replaced by what is there now. Would've thought there would be an index error otherwise.
    while ttest == 0 and v != len(trun_versions):
        # print "TESTING TRUN_VERSION = " + str(trun_versions[v])
        if trun_versions[v] not in primes:
            # print "NOT FOUND"
            ttest = 1
        v += 1

    if ttest == 0: #or n != 29 or n != 59 or n != :
        # print "TRUN_PRIME"
        trun_primes.append(t)
        print trun_primes
        # print "TRUN_PRIMES = " + str(trun_primes)
        return True
    else:
        # print "NOT TRUN_PRIME"
        return False

n = primes[len(primes) - 1] + 2
while len(trun_primes) != 11:
    # print "n = " + str(n)
    ptest = 1
    i = 0
    while ptest != 0 and i != len(primes) - 1:
        p = primes[i]
        # print "p = " + str(p)
        ptest = n % p
        # print "n % p = " + str(n % p)
        i += 1
    if ptest == 0:
        # print "NOT PRIME"
        n += 2
    else:
        primes.append(n)
        # print "PRIME"
        # print "PRIMES = " + str(primes)
        test_trun(n)
        n += 2
    # print ""

print sum(trun_primes)
# Answer: 748317
# Truncatable Primes: 23, 37, 53, 73, 313, 317,
# 373, 797, 3137, 3797, 739397