Detailed mathematical approach

Problem Summary

A two-sided truncatable prime is a prime number that stays prime after repeatedly deleting digits from the left and also after repeatedly deleting digits from the right. The single-digit primes \(2,3,5,7\) are excluded, so the search starts with multi-digit candidates only.

The goal is to find the 11 such numbers in base 10 and add them. The implementations use the fact that the problem statement guarantees there are exactly 11 solutions, so the search can stop as soon as the eleventh one is found. The resulting sum is \(748317\).

Mathematical Approach

There is no recurrence or hidden closed form here. The central mathematical object is the decimal expansion of a prime and the invariant that every proper prefix and every proper suffix of that expansion must also be prime.

Prefixes and suffixes define the property

Let

$p = d_1 d_2 \cdots d_k$

be the decimal representation of a \(k\)-digit prime. For each cut position \(c=1,2,\dots,k-1\), define the right truncation and left truncation by

$R_c = \left\lfloor \frac{p}{10^c} \right\rfloor,$

$L_c = \text{the integer represented by } d_{c+1} d_{c+2} \cdots d_k.$

Then \(p\) is truncatable exactly when

$p,\ R_1,\dots,R_{k-1},\ L_1,\dots,L_{k-1}$

are all prime. In other words, every proper prefix and every proper suffix of the decimal string must be prime. This is the precise condition checked by the C++, Python, and Java implementations.

Immediate digit restrictions

Some digits are impossible before any search begins. The first digit \(d_1\) must be one of \(2,3,5,7\), because after enough right truncations only that digit remains. The last digit \(d_k\) must be \(3\) or \(7\): it must itself be prime after all left truncations, but a multi-digit prime cannot end in \(2\) or \(5\).

Every interior digit must belong to \(\{1,3,7,9\}\). The reason is that each interior digit becomes the last digit of some proper prefix, and every such prefix must be prime. An even interior digit or a \(5\) would force one of those prefixes to be composite. These restrictions explain why valid examples are rare.

Why the implementations can scan odd numbers

Since every truncatable prime in this problem has at least two digits, it is odd and larger than \(10\). Therefore the search may begin at \(11\) and advance by \(2\), never missing a valid answer. For each odd candidate \(n\), the algorithm first checks whether \(n\) itself is prime. Only then does it examine all cut positions.

The stopping rule comes directly from the problem statement: there are exactly 11 truncatable primes. So the search is not based on a guessed numerical limit; it terminates when the count reaches 11.

Worked examples

The standard positive example is \(3797\). Its right truncations are

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

and its left truncations are

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

Every number in both chains is prime, so \(3797\) is truncatable.

A useful contrast is \(47\). It is prime, and its left truncation is \(7\), which is prime, but its right truncation is \(4\), which is not prime. So being prime is far from sufficient; both truncation directions must survive every cut.

How the Code Works

Primality testing by trial division

The implementation uses a direct primality test. Numbers below \(2\) are rejected immediately. Even numbers are prime only when the number is \(2\). For an odd candidate \(n\), the code tries odd divisors \(3,5,7,\dots\) up to the point where \(p \le n/p\), which is equivalent to \(p^2 \le n\). If no divisor is found, the number is prime.

Testing one candidate for truncatability

If \(n<10\), the candidate is rejected because single-digit primes are excluded by the problem. Otherwise the decimal representation is converted to a string once. For each cut position, the suffix after the cut and the prefix before the cut are parsed back into integers. Both are sent to the primality test, and the candidate is rejected at the first composite truncation.

This mirrors the mathematical definition exactly: each cut produces one proper suffix and one proper prefix, and both must remain prime.

The outer search loop

The search keeps two running values: how many truncatable primes have been found and the sum of those values. Starting from \(11\), it inspects only odd integers. Whenever a candidate passes the truncation test, the count is increased and the candidate is added to the running total. As soon as the count reaches 11, the algorithm returns the sum.

The implementations also include two lightweight sanity checks: \(3797\) must be accepted, while \(47\) must be rejected. Those checks confirm that both truncation directions are being enforced.

Complexity Analysis

For a single integer \(n\), the trial-division primality test costs \(O(\sqrt{n})\) time and \(O(1)\) extra space. If \(n\) has \(k\) digits, the truncatability test performs one primality check on \(n\) itself and then two more for each cut position, for a total of \(2k-1\) primality tests. That gives \(O(k\sqrt{n})\) time for one candidate, with \(k = O(\log n)\).

If \(M\) is the largest odd number examined before the eleventh solution appears, the full search remains practical because only odd numbers are tested and most candidates fail quickly. A clean upper bound is \(O(M^{3/2})\) time for the whole scan with \(O(1)\) auxiliary memory, aside from temporary decimal strings of length \(O(\log M)\). For this problem, that is easily fast enough.

Footnotes and References

1. Project Euler Problem 37: https://projecteuler.net/problem=37
2. Truncatable prime: Wikipedia - Truncatable prime
3. Prime number: Wikipedia - Prime number
4. Trial division: Wikipedia - Trial division
5. Decimal positional notation: Wikipedia - Decimal