[Math] How was the 506-digit prime number 999…9998999…999 found

prime numbers

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.

Best Answer

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.
Related Question