A Fun Exercise in Truncatable Primes
/The other day, a tweet popped up in my time line.
73939133 is the largest prime number with this curious property: if you take one or more digits off the end, the resulting numbers are all prime. pic.twitter.com/clwgA9jIiz
— Fermat's Library (@fermatslibrary) December 10, 2017
Now this has me thinking if there might be a larger one. Given there are infinite prime numbers, why wouldn’t there be another larger one? Unless it has to be built from this one. Curious math question. https://t.co/IUKujDkfoK
— Tom Bredemeier (@TomBredemeier) December 10, 2017
Huh. Did he have a point? Infinity is quite large. Is this the equivalent of ATP’s on an infinite timescale?
NOTE: I discovered later that these prime numbers are called truncatable primes. The ones where you remove digits on the right side are specifically called righttruncatable primes.
What if we think about it from a software developer’s point of view? How can we design an algorithm to generate – potentially endlessly – all prime numbers that exhibit this characteristic?
Let’s try a simple approach. Instead of searching for large truncatable primes, let’s build them from smaller ones. By building the prime numbers up one digit at a time, we can guarantee that the algorithm will only generate truncatable primes.
In the beginning, there were single digit prime numbers[1]:
primes = [2, 3, 5, 7, 9]
Then, we need to define the possible digits that can be appended to these to make larger primes. For instance, take the first prime in the list 2
. Let’s start appending digits to the right to see if we can make larger prime numbers.
initial prime  new digit  combined  prime? 

2  1  21  no 
2  2  22  no 
2  3  23  yes 
etc… 
Quickly we can toss out all even digits, as any number ending in an even digit is divisible by 2
. Additionally, we can leave out 5
as any number ending in a 5
is divisible by 5
.
This leaves us with the following possibilities to append to the end of our prime numbers:
appendable_digits = [1, 3, 7, 9]
That’s not too bad. Nice and short.
Now we can create new primes by:
 Taking the first number in
primes
 Trying to create new prime numbers by appending each of the digits in
appendable_digits
 If the new number is a prime number, add it to
primes
 Once all combinations with
appendable_digits
have been tried, go back to step #1
In pseudocode, it would look something like this:
# empty list to hold the final truncatable primes truncatable_primes = [] while len(primes): # get the first prime number in the list one_prime = primes[0] # loop through the appendable digits for digit in appendable_digits: # create a new potential prime by adding the digit to the right potential_prime = one_prime * 10 + digit # check if the created number is prime if is_prime(potential_prime): # add it to the end of the primes list primes.append(potential_prime) # add the original prime to our final output list truncatable_primes.append(one_prime) # and remove it from the primes list, so we don't keep checking it primes = primes[1:]
Besides the is_prime
function, which isn’t shown, this pseudocode is actually runnable Python code.
So I ran it.
And here’s the thing. Since it’s building the list of truncatable prime numbers from the ground up, if there were an infinite number of them, the program would never end.
But… it ended.
Here is the final truncatable_primes
list:
[2, 3, 5, 7, 9, 23, 29, 31, 37, 53, 59, 71, 73, 79, 97, 233, 239, 293, 311, 313, 317, 373, 379, 593, 599, 719, 733, 739, 797, 971, 977, 2333, 2339, 2393, 2399, 2939, 3119, 3137, 3733, 3739, 3793, 3797, 5939, 7193, 7331, 7333, 7393, 9719, 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]
If there were any larger righttruncatable primes out there, they would have to be built from the longest of these numbers. However, since we’ve exhaustively tried appending all digits to the end of them that could make a prime number, we know that we have generated all existing righttruncatable primes. 73939133
is, indeed, the largest.
This isn’t the normal theme to my blog posts, but it was a fun exercise to try.
You can find me on Twitter. I’m @yonomitt.
Have a nice day,
Yono

…and they were good. ↩