// you’re reading...
(1 votes, average: 5.00 out of 5)
Loading ...

Project Euler Problem 37 Solution

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

When a prime number, greater than 100, is truncated, it can’t be composed of any digits from the set {2, 4, 5, 6, 8, 0} or the truncated number would be composite. Further, it can’t start or end with 1 or 9 or a truncated version would end up being composite. Finally, any prime having pairs as ’11′, ’33′, ’77′ or ’99′ would eventually be divisible by 11 and therefore composite.

By applying this observation, we could truncate(sorry) our original list of primes from 78,473 to 65 primes. After looking at the list you immediately see you could eliminate entries ending in 93 or beginning with 39 leaving only 40 primes left to check. You could keep going and easily solve this one by hand.

So, outside the program presented here, we built the list of 40 prime numbers using the regular expression:
``` @p = grep {!/[024568]/ && !/99|77|33|11/ && !/^[91]/ && !/[91]\$/ && !/93\$/ && !/^39/} @primes; ```

We didn’t forget to add the two-digit truncatable primes. We found them by hand: 23, 37, 53, 73

Solution

Runs < 1 second in Python.

```from Euler import is_prime from math import log10   primes = [23,37,53,73,313,317,373,797,3137,3797,7937,31397,31973,37313,37397,71317, 71713,71917,73973,79397,313717,317197,319313,371737,371797,373717,373937, 379397,713737,713917,717317,717397,717917,719197,719713,719717,731713, 731737,739373,739397,791317,791797,793717,797917]   def trunc(n): c = n while c>10: c = c % 10**(int(log10(c))) n = n//10 if not is_prime(c) or not is_prime(n): return False return True   c = 0 s = 0 for p in primes: if trunc(p): print p c += 1 s += p   print c,"primes found for a sum of",s```

Comments

Didn’t have fun with this one. Here’s the start of our regex code to sift out the 11 primes from a file of primes. It reduces the list of 78,499 primes from 2 – 1,000,000 to just 28. Not up to finishing it.
``` open IN, "<primes35.txt"; @p = grep {!/[024568]/ && /[37]\$/ && /^(3[17][^1]|7[39][^13])/ && !/99|77|33|11/} ; ```

Discussion

9 Responses to “Project Euler Problem 37 Solution”

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

Posted by Mike | March 4, 2012, 7:22 PM
2. 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
3. Thanks for both your response and understanding. You’re one of the good ones.

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

Posted by dingo | November 4, 2012, 12:34 PM
5. ```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)[0] in e[2:] or str(p)[0] == '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

Trackbacks/Pingbacks

1. [...] like any of the solutions to the problem. However it was the best I could come up with. Over at DreamShire he takes an approach of filtering a list of primes based on a set of rules of when a number can be [...]