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())

• vnp: Strictly speaking, you don't need a program to solve the challenge. It is easy to observe that there are 8 truncatable primes below 100, and the challenge itself gives up the other three (379, 797 and 3797).
• RKJ: Nice observation ! although i would still prefer to do it using python.
• Peter Taylor: @vnp, there are only four below 100, so you're still missing four.

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?

• RKJ: Thanks ! Didn't know that using sets makes such a difference.

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.