15
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Source? $ $ $ $ $\endgroup$ – Did Feb 8 '16 at 7:33
  • 4
    $\begingroup$ Would you be so kind to write it in a human-readable fashion as $10^a-10^b-1$? (From what ispseudoprime()tells me, it should be $10^{506}-10^{253}-1$, I suppose? $\endgroup$ – Hagen von Eitzen Feb 8 '16 at 7:39
  • $\begingroup$ @Did video link $\endgroup$ – Omnomnomnom Feb 8 '16 at 7:48
  • $\begingroup$ Regarding your last sentence: The sequence of primes goes $2,3,5,7,\ldots, p-378,p,p+2054,\ldots$ $\endgroup$ – Hagen von Eitzen Feb 8 '16 at 7:49
  • 2
    $\begingroup$ +1, very interesting question. Makes me wonder what is the largest known prime number which does not belong in any specific well defined class such as the ones that you've mentioned (Mersenne, Fermat, etc). $\endgroup$ – barak manos Feb 8 '16 at 7:55
11
$\begingroup$

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.
$\endgroup$
2
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.