# Project Euler Problem 37: Truncatable Primes¶

The source code for this problem can be found here.

## Problem 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 Discussion¶

Enumerate the prime numbers in ascending order, testing each in term for the truncatable property. For each truncatable prime, accumulate their sum until eleven have been accounted for.

Note

due to the implementation of lib.sequence.Primes(), an upper-bound must be provided. This meant trial and error was required to identify an appropriate bound before the code below was correct.

## Solution Implementation¶

from typing import Set

from lib.digital import num_digits
from lib.sequence import Primes

def is_truncatable_prime(value: int, primes: Set[int]) -> bool:
""" Test whether value is both left to right and right to left truncatable or not

:param value: the integer to test
:param primes: a set of primes containing at least those in the range :math:[2, value]
:return: whether value is truncatable or not
"""

# Check for right to left truncatable
temp = value
while temp >= 10:
temp //= 10
if temp not in primes:
return False

# Check for left to right truncatable
while num_digits(value) > 1:
value %= 10 ** (num_digits(value) - 1)
if value not in primes:
return False

return True

def solve():
""" Compute the answer to Project Euler's problem #37 """
upper_bound = 740000  # found by trial and error
primes = set(Primes(upper_bound=upper_bound))
multidigit_primes = filter(lambda p: p >= 10, primes)
truncatable_primes = filter(lambda p: is_truncatable_prime(p, primes), multidigit_primes)

solutions.problem37.is_truncatable_prime(value, primes)
Parameters: value (int) – the integer to test primes (Set[int]) – a set of primes containing at least those in the range $$[2, value]$$ bool whether value is truncatable or not
solutions.problem37.solve()