This one was quite fun.
Problem:-
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.
Solution:-
Again its a brute force ( takes a while to get the last prime) ,
I use a generator I found online to get the list of primes and then check if it left and right truncatable.
import time
from itertools import ifilter, count
def isPrime(n):
if n == 1:
return False
i = n - 1
while i > 1:
rem = n % i
if rem == 0:
return False
else:
i = i - 1
return True
def truncateLeft(num):
k = num
while k != 0:
k /= 10
if not isPrime(k):
return False
return True
def truncateRight(num):
k = num
while k != 0:
k %=(10**(len(str(k))-1))
if not isPrime(k):
return False
return True
def sieve():
g = count(2)
while True:
prime = g.next()
yield prime
g = ifilter(lambda x, prime=prime: x % prime,g)
candidates = []
t = time.time()
primes = sieve()
start = primes.next()
while len(candidates) != 11:
if truncateLeft(start) and truncateRight(start) and start > 7:
candidates.append(start)
print str(start) + " has been added"
start = primes.next()
print sum(candidates)
print time.time() - t
