Project Euler Problem 37 in Python

Question

Project Euler Problem 37 asks:

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.

My approach can generate first 8 numbers "fairly" quickly and it relies on pregenerated list of primes created using sieve of eratosthenes. I've tried with active prime generation but it was slower, any way to optimize this code ?

from algorithms import *

primes = [i for i in gen_primes(10000000)]


def is_truncatable_right(n):
    a = True
    if n > 10:
        for x in range(len(str(n))):
            if int(n) not in primes:
                a = False
            n = str(n)[:-1]
        return a
    else:
        return False


def is_truncatable_left(n):
    a = True
    if n > 10:
        for x in range(len(str(n))):
            if int(n) not in primes:
                a = False
            n = str(n)[1:]
        return a
    else:
        return False


def main():
    n = []
    a = 11
    while len(n) != 11:
        if is_truncatable_left(a) and is_truncatable_right(a):
            n.append(a)
        a += 1
    return n, sum(n)


print(main())

Answer 1

Use the right data structure for the job. If you have

            if int(n) not in primes:

called more than a small constant number of times then primes should not be a list. If you change

primes = [i for i in gen_primes(10000000)]

to

primes = set(i for i in gen_primes(10000000))

you will see a significant speedup.

---

The algorithm could also be improved. I don't want to go into too much detail here because that's not in keeping with the ethos of Project Euler, but I think I can give you a couple of hints:

The problem statement says that there are only eleven primes matching the criterion. What property of primes with the criterion allowed them to prove that? How can you apply that property to generate them faster?

If you have found all of the truncatable primes of length n, do you need to loop over all truncations of a candidate number of length n+1?

Answer 2

One thing you could do to increase the speed of your algorithm would be to use the numbers in primes rather than incrementing a and then checking if a is in primes.

Ex.

Since we know that 11 is the 5th prime number, we could set a = 4, and then pass primes[a] to your truncation functions.

You'd still be incrementing a, but you would know that you're already using a valid prime number, because it comes from the list of primes you already generated.

P.S. Using this method, you could effectively skip your first check in both for loops for every case, although you will have to re-write them to accommodate this change.