Saturday, December 29, 2007

Project Euler 39

After a long time , but here is another project euler problem that I worked on.

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