Right-Truncatable Primes in R

A prime number may have the property that (given its decimal numeral) successively deleting rightmost digits (if any) of the numeral always results in a numeral denoting a prime number. An example is the prime 739. For 73 is prime and 7 is prime. Such primes are called right-truncatable primes. A similar, slightly more complicated, definition applies in the opposite direction, yielding left-truncatable primes. Together they are known as truncatable primes. (See also here.)

There are exactly 83 right-truncatable primes:

2, 3, 5, 7, 23, 29, 31, 37, 53, 59, 71, 73, 79, 233, 239, 293, 311, 313, 317, 373, 379, 593, 599, 719, 733, 739, 797, 2333, 2339, 2393, 2399, 2939, 3119, 3137, 3733, 3739, 3793, 3797, 5939, 7193, 7331, 7333, 7393, 23333, 23339, 23399, 23993, 29399, 31193, 31379, 37337, 37339, 37397, 59393, 59399, 71933, 73331, 73939, 233993, 239933, 293999, 373379, 373393, 593933, 593993, 719333, 739391, 739393, 739397, 739399, 2339933, 2399333, 2939999, 3733799, 5939333, 7393913, 7393931, 7393933, 23399339, 29399999, 37337999, 59393339, 73939133

I’m using the following packages (“numbers” for the Miller-Rabin primality test)

library(stringr)
library(numbers)
library(gmp)
library(microbenchmark)

The following function in the programming language R generates all the right-truncatable primes:

make.rtp <- function(num.digits) {
sols <- function(X) {
Y <- c(10*X+1, 10*X+3, 10*X+7, 10*X+9)
Y[unlist(lapply(Y, miller_rabin))]
}
L <- list()
L[[1]] <- c(2,3,5,7)
if (num.digits > 1) {
for (i in 1:(num.digits-1)) {
e <- sols(L[[i]])
L[[i+1]] <- e[order(e)]
}
}
unlist(L)
}

Then one obtains the full list very quickly (around 31 milliseconds) by running:

make.rtp(8)

It’s easy to see that the largest is the 8-digit 73939133 and there are no larger ones.