Last night on Twitter one of my favorite accounts, @fermatslibrary, put up an interesting post:
Start with 82 and go backwards to 1
8281807978777675747372717069686
7666564636261605958575655545352
5150494847464544434241403938373
6353433323130292827262524232221
2019181716151413121110987654321
…this number is prime!
— Fermat’s Library (@fermatslibrary)
November 20, 2019
Start at 82 and write it down, then 81, write that down, etc. until you reach one, and you’ve written a (huge) prime number. Wow!
This seemed so strange to me, so of course I got curious:
Do we know if this occurs using any other numeric base?
I’ll probably write a program to find out because I’m a huge nerd and things like this stick in my head far longer than they should… ugh. THANKS FOR DISTRACTING ME AHHHHH!
— zxq9 (@zxq9_notits)
November 20, 2019
After some doodling around I wrote a script that checks whether numbers constructed by the method above are prime numbers when the number construction is performed in various numeric bases (from 2 to 36, limited to 36 because for now I’m cheating using Erlang’s integer_to_list/2). It prints the results to the screen as the process handling each base finishes and writes a text file “texty_primes-result-[timestamp].eterms” at the end for convenience so you can use file:consult/1 on it later to mess around.
There are a few strange aspects to large primes, one of them being that checking whether or not they are prime can be a computationally intense task (and nobody knows a shortcut to this). To this end I wrote the Miller-Rabin primality test into the script and allow the caller to decide how many rounds of Miller-Rabin to run against the numbers to check them. So far the numbers that have come out have matched what is expected, but once the numbers get extremely large (and they get pretty big in a hurry!) there is only some degree of confidence that they are really prime, so don’t take the output as gospel.
I wrote the program in Erlang as an escript, so if you want to run it yourself just download the script and execute it.
The script can be found here: texty_primes
A results file containing the (very likely) prime constructions in bases 2 through 36 using “count-back from X” where X is 1 to 500 can be found here: texty_primes-result-20191121171755.eterms
Analyzing from 1 to 500 in bases 2 through 36 took about 25 minutes on a mid-grade 8-core system (Ryzen5). There are some loooooooooong numbers in that file… It would be interesting to test the largest of them for primality in more depth.
(Note that while the script runs you will receive unordered “Base X Result” messages printed to stdout. This is because every base is handed off to a separate process for analysis and they finish at very different times somewhat unpredictably. When all processing is complete the text file will contain a sorted list of {Base, ListOfPrimes} that is easier to browse.)
An interesting phenomenon I observed while doing this is that some numeric bases seem simply unsuited to producing primes when numbers are generated in this manner, bases that themselves are prime numbers in particular. Other bases seem to be rather fruitful places to search for this phenomenon.
Another interesting phenomenon is the wide number of numeric bases in which the numbers “21”, “321”, “4321” and “5321” turn out to be prime. “21” and “4321” in particular turn up quite a lot.
Perhaps most strangely of all is that base 10 is not a very good place to look for these kinds of primes! In fact, the “count back from 82” prime is the only one that can be constructed starting between 1 and 500 that I’ve found. It is remarkable that anyone discovered that at all, and also remarkable that it doesn’t happen to start at 14,562 instead of 82 — I’m sure nobody would have noticed this were any number much higher than 82 the magic starting point for constructing a prime this way.
This was fun! If you have any insights, questions, challenges or improvements, please let me know in the comments.