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 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:
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?|
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
This leaves us with the following possibilities to append to the end of our prime numbers:
That’s not too bad. Nice and short.
Now we can create new primes by:
- Taking the first number in
- Trying to create new prime numbers by appending each of the digits in
- If the new number is a prime number, add it to
- Once all combinations with
appendable_digitshave been tried, go back to step #1
In pseudocode, it would look something like this:
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
[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,
…and they were good. ↩