Project Euler Solution 37: Truncatable primes

This time we have Problem 37: Truncatable primes, which is about prime numbers that stay primes even if one removes digits from the left or right.

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.

Here we can also use the insight from Solution 35: Circular primes that even digits and 5 at the end of a number will prevent the number from being a prime. There is now an exception for the first digit as 23 can be truncated into 2 and that is a fine prime number.

I've written a generator for truncations such that this is encapsulated. I needed to write a test in order to get it right with all the slices.

def iter_truncations(number: int) -> int:
    s = str(number)
    for i in range(1, len(s)):
        yield int(s[i:])
        yield int(s[:-i])


def test_iter_truncations() -> None:
    truncations = list(iter_truncations(1234))
    assert truncations == [234, 123, 34, 12, 4, 1]

For the primes I first tried the generator, but that is too slow. We need to use the prime sieve from Solution 7: 10001st prime again. The limit of a million was just guessed.

def solution() -> int:
    primes = prime_sieve(1_000_000)
    truncatable_primes = []
    for prime in primes:
        if prime < 10:
            continue
        if set(str(prime)[1:]) & {"0", "2", "4", "5", "6", "8"}:
            continue
        for truncation in iter_truncations(prime):
            if truncation not in primes:
                break
        else:
            truncatable_primes.append(prime)
            if len(truncatable_primes) == 11:
                break
    return sum(truncatable_primes)

This runs for 2.0 s, so I am happy with that solution.