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

## No comments:

Post a Comment