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)
answer = sum(truncatable_primes)
return answer
expected_answer = 748317
-
solutions.problem37.
is_truncatable_prime
(value, primes)¶ Test whether value is both left to right and right to left truncatable or not
Parameters: - value (
int
) – the integer to test - primes (
Set
[int
]) – a set of primes containing at least those in the range \([2, value]\)
Return type: bool
Returns: whether value is truncatable or not
- value (
-
solutions.problem37.
solve
()¶ Compute the answer to Project Euler’s problem #37