Project Euler Problem 37

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.

Removing digits from the right of $3797$ leaves its prefixes $379$, $37$ and $3$, and removing them from the left leaves its suffixes $797$, $97$ and $7$. A prime is right-truncatable if all of its prefixes are prime and left-truncatable if all of its suffixes are prime. A truncatable prime is then a prime with at least two digits that is both.

We'll solve the more general problem of finding all the truncatable primes in any base $b$. The original problem is $b = 10$ and the HackerRank version adds up the ones below $N$.

The problem tells us there are only eleven truncatable primes but not how we know that. We could sieve the primes below $10^6$ like in Problem 10 and check the prefixes and suffixes of every one. That will find all eleven, but we only know that $10^6$ is enough because we were told that. And unfortunately, no search up to a limit can rule out a truncatable prime with a hundred digits though. However, we can show that there are only eleven by construction!

Growing the right-truncatable primes

The trick is to not search for truncatable primes but to construct all possible ones by growing the right-truncatable primes instead. Removing the last digit of a right-truncatable prime leaves another right-truncatable prime. So from any right-truncatable prime we can peel off one digit at a time to a one-digit prime, like $3797 \to 379 \to 37 \to 3$. Read backwards, that walk starts at $3$ and appends one digit at a time while staying prime. So the right-truncatable primes form a tree! The roots are $2$, $3$, $5$ and $7$, and the children of each prime are the primes we get by appending a digit to it.

Only four digits are worth appending. Like in Problem 35, a prime with two or more digits can't end in an even digit or a $5$, so we only need to try $1$, $3$, $7$ and $9$. In base $b$ the roots are the primes below $b$, and the digits worth appending are the ones that share no factor with $b$.

We grow the whole tree breadth-first, using the array of primes found so far as its own queue. We start with the single-digit primes and go through each element of the array trying to construct right-truncatable primes. Each time we find one, we apprent it to the array. The first four steps try $21$, $23$, $27$ and $29$ after $2$, then $31$, $33$, $37$ and $39$ after $3$, and so on, leaving $23$, $29$, $31$, $37$, $53$, $59$, $71$, $73$ and $79$. So the primes are added in order and come out sorted.

using Base.Checked: checked_add, checked_mul

function find_right_truncatable_primes(; base=10)
    mr = MillerRabin()
    last_digits = [d for d in 1:base-1 if gcd(d, base) == 1]
    primes = [p for p in 2:base-1 if is_prime(p, mr)]

    i = 1
    while i <= length(primes)
        parent = primes[i]
        for d in last_digits
            child = checked_add(checked_mul(base, parent), d)
            is_prime(child, mr) && push!(primes, child)
        end
        i += 1
    end

    return primes
end

We don't know how large the numbers will get ahead of time, so instead of constructing MillerRabin with the largest number we'll test like we did in Problem 35, MillerRabin() picks the fewest witnesses for each number as it goes. The arithmetic is done in whatever integer type base is, and checked_mul and checked_add throw an OverflowError instead of silently wrapping around.

Here's the part of the tree that grows from $7$, with the truncatable primes in red:

7
├── 71 ── 719 ── 7193 ── 71933 ── 719333
├── 73
│   ├── 733
│   │   ├── 7331
│   │   └── 7333 ── 73331
│   └── 739 ── 7393 ── 73939
│                      ├── 739391 ── 7393913 ── 73939133
│                      ├── 739393
│                      │   ├── 7393931
│                      │   └── 7393933
│                      ├── 739397
│                      └── 739399
└── 79 ── 797

Maybe we shouldn't be surprised that the trees thin out and die. By the prime number theorem a number near $x$ is prime with probability roughly $1/\ln x$. But every child ends in $1$, $3$, $7$ or $9$ so it can't be divisible by $2$ or $5$, which makes it $10/4 = 2.5$ times more likely to be prime. Each right-truncatable prime has four potential children (in base $10$), so once $2.5/\ln x$ dips below a quarter each prime has fewer than one prime child on average. That happens when $\ln x > 10$, or roughly when $x > e^{10} \approx 22{,}000$, which is right where the tree stops growing: it has $16$ primes with $4$ digits but only $15$ with $5$.

Checking the suffixes

The tree takes care of the prefixes, so all that's left is checking the suffixes. The suffixes of $p$ are $p \bmod 10$, $p \bmod 100$, $p \bmod 1000$ and so on, and we check the shortest ones first since they're the cheapest to test.

function is_left_truncatable(p, base, mr)
    m = base
    while m < p
        is_prime(p % m, mr) || return false
        m *= base
    end
    return true
end

function find_truncatable_primes(; base=10)
    mr = MillerRabin()
    return [
        p for p in find_right_truncatable_primes(; base)
        if p >= base && is_left_truncatable(p, base, mr)
    ]
end

For example, $3797$ passes since $7$, $97$ and $797$ are all prime, while its parent $379$ fails straight away since $9$ isn't prime.

This finds the eleven truncatable primes in 74.281 μs. Most of the 61.41 KiB it allocates comes from MillerRabin() choosing the witnesses for each number on the fly.

More importantly, this proves that there are only eleven truncatable primes. The tree contains all right-truncatable primes by construction and every truncatable prime is right-truncatable, so it's somewhere in the tree.

Growing the right-truncatable primes is an old idea discussed by early solutions such as those of mvz and manishi.

The truncatable primes are OEIS A020994, which includes the one-digit primes. The right- and left-truncatable primes are OEIS A024770 and OEIS A024785. How many of them have each number of digits is in OEIS A050986 and OEIS A050987. The $83$ right-truncatable primes and $4{,}260$ left-truncatable primes have been known since the 1970s (Angell, 1977), which SidneyLyZhang pointed out in the forum thread.

There are other ways to truncate a prime too. Removing a digit from either end at each step gives $149{,}677$ left-or-right-truncatable primes (OEIS A137812), and removing a digit from both ends at once gives $920{,}720{,}315$ primes (OEIS A077390), the largest of which has $104$ digits.

Other bases

Nothing we did depends on base $10$, and find_truncatable_primes(base=b) works in any base. The catch is how big the numbers get. We have to grow the whole tree, and in larger bases it gets much deeper even though the truncatable primes themselves stay small. Int64 is enough for every base up to $16$ except $14$, while bases $17$ to $30$ all need BigInt.

Here are all the bases up to $30$, not counting the one-digit primes as truncatable. The counts match OEIS A076586 and OEIS A323390 (which counts the one-digit primes), and the largest truncatable primes match OEIS A323137.

The odd bases stand out: they have far fewer truncatable primes than the even bases, and never any primes with more than three digits. That's because in an odd base, a number is odd when its digit sum is odd. In a truncatable prime, every prefix and suffix with at least two digits is an odd prime, so its digit sum is odd. But with four or more digits, the first two digits (a prefix) and the rest (a suffix) would each have an odd digit sum, making the total even. So a truncatable prime in an odd base has at most three digits. Even bases don't have this problem since the parity of a number only depends on its last digit.

References