A Fun Exercise in Truncatable Primes

/

The other day, a tweet popped up in my time line.

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 right-truncatable 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:

  1. Taking the first number in primes
  2. Trying to create new prime numbers by appending each of the digits in appendable_digits
  3. If the new number is a prime number, add it to primes
  4. 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 right-truncatable 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 right-truncatable 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

  1. …and they were good.  ↩