Project Euler Problem 37

Solution

Answer: 748317

1. Mathematical analysis

We seek the only eleven primes that are:

prime themselves,
remain prime when repeatedly truncating digits from left to right, and
remain prime when repeatedly truncating digits from right to left.

Example:

$$3797 \to 797 \to 97 \to 7$$

and

$$3797 \to 379 \to 37 \to 3$$

all remain prime.

We must find the sum of all such primes, excluding $2,3,5,7$.

Key observations

Observation 1: Digit restrictions

For any multi-digit truncatable prime:

The last digit must be $3$ or $7$, since primes $>5$ cannot end in even digits or 5.
Internal digits cannot be even or 5, otherwise some truncation would become composite.

Thus candidates only use digits from:

$${1,3,7,9}$$

(except possibly the leading digit).

This dramatically reduces search space.

Observation 2: Truncation tests

For a number $n$, define:

Right truncation

Repeatedly remove the last digit:

$$3797,\ 379,\ 37,\ 3$$

This is easy using integer division by 10:

n
n // 10
n // 100
...

All must be prime.

Left truncation

Repeatedly remove the first digit:

$$3797,\ 797,\ 97,\ 7$$

This can be checked by converting to a string and slicing:

"3797"
"797"
"97"
"7"

All resulting integers must be prime.

Observation 3: There are only eleven

The problem guarantees there are exactly 11 such primes, so we can:

Generate primes,
Test truncatability,
Stop once we find eleven.

Efficient primality testing

We use trial division up to:

$$\sqrt{n}$$

since if $n = ab$, at least one factor is at most $\sqrt n$.

Algorithm:

reject $n<2$,
handle even numbers quickly,
test odd divisors up to $\sqrt n$.

Complexity is tiny because there are only 11 valid numbers.

2. Python implementation

import math

def is_prime(n):
    """Return True if n is prime."""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    limit = int(math.sqrt(n))
    for d in range(3, limit + 1, 2):
        if n % d == 0:
            return False
    return True

def is_truncatable_prime(n):
    """Check if n is truncatable from both directions."""
    s = str(n)

    # Exclude single-digit primes
    if len(s) == 1:
        return False

    # Left-to-right truncations
    for i in range(len(s)):
        if not is_prime(int(s[i:])):
            return False

    # Right-to-left truncations
    for i in range(len(s), 0, -1):
        if not is_prime(int(s[:i])):
            return False

    return True

found = []
n = 11  # smallest possible multi-digit prime

while len(found) < 11:
    if is_prime(n) and is_truncatable_prime(n):
        found.append(n)
    n += 2  # skip even numbers

answer = sum(found)

print(found)
print(answer)

3. Code walkthrough

`is_prime(n)`

Checks primality efficiently.

if n < 2:
    return False

Rejects non-primes.

if n == 2:
    return True
if n % 2 == 0:
    return False

Handles even numbers quickly.

for d in range(3, limit + 1, 2):

Checks only odd divisors up to $\sqrt n$.

`is_truncatable_prime(n)`

First:

s = str(n)

Convert number to a string for slicing.

Single-digit primes are excluded:

if len(s) == 1:
    return False

Left truncations

for i in range(len(s)):
    int(s[i:])

For 3797:

3797
797
97
7

All must be prime.

Right truncations

for i in range(len(s), 0, -1):
    int(s[:i])

For 3797:

3797
379
37
3

Again, all must be prime.

Small example verification

Testing 3797:

Left:

$$3797,\ 797,\ 97,\ 7$$

all prime ✓

Right:

$$3797,\ 379,\ 37,\ 3$$

all prime ✓

So the test correctly accepts the example.

Running the full search produces:

$$23,\ 37,\ 53,\ 73,\ 313,\ 317,\ 373,\ 797,\ 3137,\ 3797,\ 739397$$

Their sum is:

$$748317$$

4. Final verification

Exactly 11 numbers found ✓
Excludes $2,3,5,7$ ✓
Includes the example $3797$ ✓
Sum magnitude is reasonable (dominated by $739397$) ✓

Answer: 748317