Steady primes

An Ulam spiral of size 201x201 showing distinct concentrations of primes along diagonal and horizontal lines throughout the image. (Public domain CC0 license by Morn — Own work, CC0, https://commons.wikimedia.org/w/index.php?curid=130815496

Update: There are two additional posts on this topic. The first is on digit frequency in right-truncatable primes in base 10, and the second is on right-truncatable primes in other bases.

The image above shows an Ulam spiral, a doodling artifact originally created by Stanislaw Ulam that uncovered some surprising properties of primes.

I’ve been fascinated by prime numbers since I was a student in junior high school (that’s middle school for you Gen-Xers and younger). I’ve long dreamt of making an Ulam-like discovery on my own, but of course I’m a dilletante and the territory has been well worked by professionals with better training and bigger brains than me!

Nevertheless, I dabble, and I recently dabbled up something I think is kind of interesting.

I invented a concept I call a steady prime. The way it works is this: You write down a single digit. If it’s prime, you get to continue. You add another digit. If the complete number is still prime, you get to continue. And so on.

For example, the sequence

2
23
239
2393

is steadily prime because each of the numbers in the sequence is prime.

I bet that this concept already exists in the literature, but I was interested enough in it that I decided not to look for it. I wanted to play with the idea on my own for a while!

(Update: It does! The On-line Encyclopedia of Integer Sequences calls these “right-truncatable primes.” Thanks to my numerate friend Tom White for finding and sharing the reference.)

Once you have a steady prime, you get to keep adding digits until you can’t add any other digits and still have a prime number. I call that a terminal steady prime. It’s sort of the dead end for that sequence.

I got to wondering: How long could you keep adding digits? What’s the longest terminal steady prime? How many terminal steady primes are there?

I decided to write some computer programs to see.

I had an implementation of the Sieve of Eratosthenes laying around that I’d written for a clock project that I worked on a while ago. I ran it and computed the first ten million prime numbers. I then wrote another program to find steady primes. It did a brute-force search, starting with each single-digit prime, adding a single digit to it and checking if that were also prime by looking it up in the list of ten million primes. That continued, recursively, until I found a terminal steady prime.

My intuition was that terminal steady primes wouldn’t be that long. You only needed a gap of ten numbers, from xxxx0 to xxxx9, with no primes to shut down a particular steady prime sequence.

It turns out that ten million primes wasn’t enough to find the limit, though! While I was running that brute-force search, I found candidates that were bigger than the biggest prime I’d computed.

Rather than get clever, I just got more brutal in my brute force search. I recompiled my sieve program to compute the first hundred million primes, and then did my steady prime search using that table.

This time I succeeded! I exhaustively searched for terminal steady primes and verified that they all end before I get to the hundred millionth prime number.

Here’s a list of all the terminal steady primes:

23333
23339
23399339
2393
2399333
29399999
31193
31379
317
37337999
373393
37397
3793
3797
53
59393339
593993
599
719333
7331
73331
73939133
7393931
7393933
739397
739399
797

No 4, 6, 8 or 0 digits, of course; if you added one of them as the next digit to a steady prime, it’d be even, so not prime. The only 2s are in the first position, of course, befitting the unique status of the only even prime! Same for 5 — it has to be the first digit, or it’ll be a divisor of the number that ends in 5.

The density of 3s and 9s in there surprises me a little bit. I’d have guessed up front that you’d see a pretty even mix of 1s, 3s, 7s and 9s. You sure don’t! I want to think about that a little more.

Another funny thing — coincidental, I bet, but it smells a little like The Matrix — is that there are 27 terminal steady primes, and 27 is 3 cubed, or 3 times 9, and 3 and 9 show up so much in the list. Woo woo!

I wonder a little bit about how terminal steady primes behave in other number bases. Intuitively, it seems like terminal steady primes in higher bases — base 16, base 20, base 8,000,003 —will be larger numbers. I haven’t quite convinced myself that they ought to be longer — composed of more digits — as well. I want to noodle on that some, and might write more computer programs to test it out.

(Update: I’ve posted a histogram showing the decimal digit frequency in steady primes.)

The hundred millionth prime number, by the way, is 2038074743. I’ve got the whole collection in a text file on my laptop in case I need a bunch of them in a hurry.