How was the 506-digit prime number 999...9998999...999 found?

Question

I was surprised to encounter a claim made on the internet that the following number is prime:

99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999989999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

It's all 9s except for one 8. This 506-digit number didn't look especially prime to me. I couldn't find it in any publicly available lists (which clonk out around 8 or so digits), so I did trial division up to 626543489 and then did Miller-Rabin with 5000 rounds (way overkill). It seems, in-fact, to be prime.

---

My question is--is there anything significant about this number that would help us realize that it is prime? How was it found?

It's not a Mersenne, Fermat, or Perfect prime, for instance. It's not particularly large (the largest known as of this writing is in the tens of millions of digits), but I suspect the previous and next prime numbers aren't known.

Answer 1

It can be proved prime using Elliptic Curve Primality Proving; I checked using Primo which only takes a few seconds.

How they found it? The process probably was:

• Make a list of interesting-looking numbers.
• Filter the list using trial division.
• On the remaining numbers, use a fast pseudo-primality test (e.g. Fermat's test).
• Check the ones that pass the pseudo-primality test using Primo.

Answer 2

At first I thought it was a palindromic prime. There are lots of variations, and the largest currently known has 474,501 digits (Wikipedia seems to be out of date -- see The Prime Pages). For the top 3, they have some form M+1 where M is mostly factorable, hence a BLS75 n-1 proof can be done.

We can find palindromic primes of this sort with lots of tools, for example:

perl -Mntheory=:all -E '$s=8; for (1..3000) { $s="9${s}9"; say if is_prime($s); }'

finds quite a few examples including the 757 digit prime formed by an eight with 378 nines on each side. There are lots of proof methods that work for numbers this size: WraithX's APR-CL, Alpertron's APR-CL, Pari/GP's APR-CL, my ECPP-DJ or Perl/ntheory, and Primo's ECPP, among others.

Most of those proof methods work pretty well up to 2-3k digits. Primo is the only public tool that excels past that, and has been used up to 30k digits (a long undertaking on a hefty machine).

But the example you gave isn't a palindrome since it has 252 nines on one side and 253 on the other. We can find it by replacing the $s=8 with $s=89 in the script above, along with both smaller and larger primes with the same form. If using something like Pari/GP it may be nicer to use a different way of writing the number, e.g. $10^{506}-10^{253}-1$, rather than using strings.

Lastly, we can look at http://factordb.com and see that this number has been in the database for at least 5 years, with an N+1 proof. I believe factordb as well as the primes pages uses PFGW for the proof, which unfortunately doesn't output a certificate even though one should be easily constructed during the proof (admittedly it's not hard to run it again given the factorization, but it would be nice to be able to check the certificate like we can do with Primo).

Answer 3

As mentioned by others, the prime can be written as: $$N=10^{506}-10^{253}-1$$ As such, it has a form where $N+1$ is easy to factor "to over 33%" (in fact to about 50%). This means that there is an efficient "$N+1$" primality test, also known as Brillhart-Lehmer-Selfridge test.

You mention the previous and next prime. They are not hard to find for such a modest number. With PARI/GP I find with precprime and nextprime that the preceding prime is $N-378$ and the next prime is $N+2054$. These neighbor primes do not allow a quick verification; each takes about 20 seconds to rigorously verify with PARI/GP at my machine, although specialized software like the new CM would be much faster.

It seems natural to generalize to: $$N(k)=10^{2k}-10^k-1$$ A quick search (can use PARI/GP or OpenPFGW) shows $N(k)$ is prime for $k = 1, 6, 9, 154, 253, \ldots$, and here is something to look up in OEIS where you find A265383: Numbers n such that 10^n * (10^n - 1) - 1 is prime. As of now, their data field reads:

1, 6, 9, 154, 253, 1114, 1390, 2618, 5611, 12871, 15286, 108609, 132574, 164369, 188484

More generally, numbers of form: $$F(j,k)=10^j-10^k-1,\quad j>k>0$$ will have all digits 9 except for one. Some people call them near-repdigit. With a bit of practice, you can search for them at Chris Caldwell's Prime Pages.

If you want a palindrome of this type, you need $10^{2k+1}-10^k-1$; this is A183187 and A077794.