## Project Euler 37: Find the sum of all eleven primes that are truncatable from both left to right and right to left

#### Problem Description

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.

#### Analysis

The first observation is that single digit primes are excluded from consideration of the 11-prime number set, but are required when truncating a candidate prime number. So, in the example, the last truncation of 3797 yields a single digit, 3 or 7 which like all the other truncations must be prime to qualify.

Also, it nice to know that there are only 11 primes in the entire primedom that qualify, albeit we have no idea of their magnitude. Is it possible the latest discovered Mersenne prime, with millions of digits, is one of the 11? It’s for this reason any solution that employees a prime list is making assumptions based on already knowing the answer. Yes, they run very fast, but depend on a prime list to a million or so which is prophetic if not just a blind assumption.

Well, there are some other observations. For instance, when a prime number > 100 is truncated, it **can not** be composed of any digits from the set {2, 4, 5, 6, 8, 0} or the left-to-right truncated number will eventually be composite. Numbers less than 100 are exempt from this rule because they only have two digits. So numbers like 23 which have two prime digits would clearly qualify as a truncatable prime.

By applying these observations, we could lessen the size of our search space significantly. So, off we go, searching for the 11 primes, without bounds, and wait for the results.

#### Project Euler 37 Solution

Runs < 0.450 seconds in Python 2.7.Use this link to get the Project Euler 37 Solution Python 2.7 source.

#### Comments

- Function
`is_prime`

is listed in Common Functions and Routines for Project Euler - You can’t just generate primes less than a million and hope that all 11 primes are included in that range. It’s better to keep generating primes on the fly.

*Project Euler 37 Solution last updated*

What about generating possible attempts by concatenating possibilities with numbers and checking if their prime. This way you do not need to test as many numbers if they are truncatable. On my computer this code runs in <0.1s. (The site's solution runs at ~0.5s)

import time

def is_truncatable(n):

for d in range(1, len(str(n))):

if not is_prime(str(n)[d:]) or not is_prime(str(n)[:d]):

return False

return True

def is_prime(n):

n = int(n)

if n == 2 or n == 3: return True

if n < 2 or n%2 == 0: return False

if n < 9: return True

if n%3 == 0: return False

r = int(n**0.5)

f = 5

while f 1:

return generate_attempts(attemptsArray,n)

else:

return attemptsArray

start = time.time()

tp = []

numbers=[‘1′,’2′,’3′,’4′,’5′,’6′,’7′,’8′,’9’]

numLen = 2

while len(tp)<11:

attemptsArray = generate_attempts(numbers[:],numLen)

for attempt in attemptsArray:

if is_truncatable(attempt):

tp.append(int(attempt))

numLen+=1

print(sum(tp))

print(time.time()-start)

my code runs in < .25s

Thanks for this. Great way to solve this problem without the use of a pre-computed prime list.

Here is quite shorter version (also in python) that is “more fun”:

#need to “pip install prime_numbers” or implement fast “generate_all_primes_up_to(upper)” function

from prime_numbers import PrimeNumbers

def truncate_left_right(num):

s = str(num)

retVal = set()

for i in range(1, len(s)):

retVal.add(int(s[i:]))

retVal.add(int(s[:i]))

return retVal

def solve(upper):

primes = set(PrimeNumbers(1000000).rwh())

trunc_primes = set()

for prime in primes:

if truncate_left_right(prime) < primes:

trunc_primes.add(prime)

return [p for p in trunc_primes if p > 7]

print sum(solve(1000000))

# please, delete previous wrongly formatted posts. Thanks 🙂

Thanks! Very clever approach!

Thanks for both your response and understanding.

Clearly I was wrong in my assumption. I saw the array of primes and jumped to the conclusion that you were giving away answers, but I now see that this is not your intention and thus thank you for your contribution to not only the Project Euler community, but also the fields of mathematics and computer science in general.

Salut!

Is it absolutely necessary to explicitly provide answers? I can understand the analysis and so forth but… I trust you can imagine why I am asking this question.

Thanks for your question.

Firstly, we don’t provide answers, but, instead, provide solutions. Giving the answers outright would defeat the purpose and spirit of the Project Euler (PE) site and that is clearly not our intention. Providing, however, our solutions gives some insight on how to solve the problems and allow discussion for improving our programs.

Also, we could not contribute to the discussion forum on PE because new posts were closed on older problems when we started this blog.

The response to our programs has always been positive and helpful. So continuing the discussion outside the PE framework should be within the purview of free speech and expression.

I hope this will help you understand our position.

Mike