Project Euler Problem 37 Solution: Truncatable Primes

Project Euler Problem 37 Statement

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.

Solution

It’s nice to know that there are only 11 primes in the entire primedom that qualify, albeit we have no idea of their magnitude. This uncertainty is why we generate primes dynamically rather than relying on a finite prime list with an arbitrary upper limit.

The core of this solution lies in two functions: is_prime and is_trunc. The is_prime function, discussed in the introduction, simply checks if a number is prime. is_trunc, on the other hand, converts the number to a string and uses slicing to remove digits from both the beginning and end, verifying the primeness of each truncated form. This function only returns True if all truncated variants are prime.

Explanation of Slicing

arr[i:]: This slice returns a sublist starting from index i up to the end of the list.
arr[:i]: This slice returns a sublist from the beginning of the list up to (but not including) index i.
Remember, this first character is arr[0].

There are some key observations: Single-digit primes are excluded from consideration. Any truncatable prime larger than 100 cannot contain digits from the set {2, 4, 5, 6, 8, 0}—such digits would yield composites when truncated from the right. Primes under 100 are exempt from this rule, as they only have two digits, so numbers like 23 with two prime digits qualify as a truncatable prime. Lastly, any original or truncated form must end in a 3 or 7.

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

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 37

HackerRank Project Euler 37 wants us to find the sum of primes that are both truncatable from left to right and right to left below N.

Python Source Code

import Euler
pc, f, tp, d = 11, 1, [], set('024568')
def is_trunc(n):
    return all(Euler.is_prime(str(n)[d:]) and Euler.is_prime(str(n)[:d]) 
        for d in range(1, len(str(n))))

while len(tp) < 11:		# number of truncatable primes
    pc += 3-f    # fast count for prime candidates
    f = -f
    if not (pc > 100 and set(str(pc)).intersection(d)):
         if Euler.is_prime(pc) and is_trunc(pc):
            tp.append(pc)

print (sum(p for p in tp if p<1000000))

Last Word

We start our prime search from 11 and check numbers of the form 6k±1 (e.g., 11, 13, 17, 19, ...), skipping other numbers because any prime greater than 3 must be in this form. This pattern arises because numbers of the form 6k, 6k+2, 6k+3, and 6k+4 are divisible by 2 or 3 and, therefore, cannot be prime.
This program takes about 0.15 seconds. Good enough for a close-ended problem.