     (11 votes, average: 5.00 out of 5) Loading...

## Project Euler 37 Solution ## 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.

• 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

## Discussion

### 9 Responses to “Project Euler 37 Solution”

1. 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)

Posted by Ignacy | November 19, 2015, 10:48 AM
2. ```def problem37():

l, m = (1000000 - 1)/2, int((1000000 ** 0.5)//1 - 1)/2
a, e, z = [True] * l, ['2', '0', '4', '6', '8'], 23
for i in xrange(m):
if a[i]:
s = i + i + 3
t = (s ** 2)/2 - 1
for j in xrange(t, l, s):
a[j] = False
for x in xrange(10, l):
if a[x]:
p, b = 2 * x + 3, True
for d in str(p)[1:]:
if d in e:
b = False
break
if b and str(p) in e[2:] or str(p) == '1' or str(p)[-1] == '1': b = False
if b:
for i in xrange(1, len(str(p))):
q = (int(str(p)[i:]) - 3)/2
r = (int(str(p)[:i]) - 3)/2
if not a[q] or not a[r]:
b = False
break
if b: z += p
return z
```

my code runs in < .25s

Posted by hkapur97 | January 2, 2013, 6:25 AM
• Thanks for this. Great way to solve this problem without the use of a pre-computed prime list.

Posted by Mike | January 3, 2013, 2:22 AM
3. 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

def truncate_left_right(num):
s = str(num)
retVal = set()
for i in range(1, len(s)):
return retVal

def solve(upper):
trunc_primes = set()
for prime in primes:
if truncate_left_right(prime) < primes:
return [p for p in trunc_primes if p > 7]

print sum(solve(1000000))

# please, delete previous wrongly formatted posts. Thanks 🙂

Posted by dingo | November 4, 2012, 12:34 PM
• Thanks! Very clever approach!

Posted by Mike | November 5, 2012, 12:59 AM
4. Thanks for both your response and understanding.

Posted by Mike | March 8, 2012, 10:51 AM
5. 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!

Posted by beclerk01 | March 8, 2012, 12:36 AM
6. 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.

Posted by beclerk01 | March 4, 2012, 4:10 PM
• 