// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (11 votes, average: 5.00 out of 5)

Project Euler Solutions

Project Euler 37 Solution

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.


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.

download arrowUse 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


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)
    return attemptsArray

    start = time.time()
    tp = []
    numLen = 2
    while len(tp)<11:
    attemptsArray = generate_attempts(numbers[:],numLen)
    for attempt in attemptsArray:
    if is_truncatable(attempt):


    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
                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
                    if b: z += p
        return z

    my code runs in < .25s

    Posted by hkapur97 | January 2, 2013, 6:25 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
    from prime_numbers import PrimeNumbers

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

    def solve(upper):
       primes = set(PrimeNumbers(1000000).rwh())
       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
  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.


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


      Posted by Mike | March 4, 2012, 7:22 PM

Post a comment