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

solutions.problem37.solve()

Compute the answer to Project Euler’s problem #37