How was the 506-digit prime number 999...9998999...999 found?
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.
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).