Problem #37 is yet another question on Project Euler that involves manipulating digits in primes. The question reads:
Project Euler Problem 37: Truncatable primes
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.
If you’ve seen my solution to some of the last few questions that have involved prime numbers, you can probably guess what I’m going to use.
Solution #1: Sieve Approach
We simply guess and check an upper bound for the 11th truncatable prime until we have found all of them. We use a Sieve of Eratosthenes to list all primes up to the upper bound and then check all primes less than the upper bound to find any ones that are truncatable. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Sieve Approach to Project Euler Problem #37
'''
import time
def sieveEratosthenes(n):
myPrimes = []
primePossible = [True]*(n+1)
primePossible[0] = False
primePossible[1] = False
for (i,possible) in enumerate(primePossible):
if possible:
for x in range(i*i, (n+1), i):
primePossible[x] = False
myPrimes.append(i)
return [primePossible,myPrimes]
def projectEulerProblemThirtySeven(n):
allPrimeInfo = sieveEratosthenes(n)
primePossible = allPrimeInfo[0]
myPrimes = allPrimeInfo[1]
truncatablePrimes = []
for p in myPrimes:
if(p>10):
s = str(p)
found = False
for i in range(1,len(s)):
if((not primePossible[int(s[i:])]) or (not primePossible[int(s[0:i])])):
found = True
break
if not found:
truncatablePrimes.append(p)
if(len(truncatablePrimes)==11):
total = 0
for x in truncatablePrimes:
total+=x
return total
else:
return -1
start = time.time()
print projectEulerProblemThirtySeven(1000000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
748317
--- 0.2643699646 seconds ---
for input of n = 1000000
'''
As shown above, the Sieve of Eratosthenes is very good when determining properties about large primes that involve smaller primes.
Thanks for reading!
The Inner Machinations of Walker 