Jaeschke's ninth

Don Reble djr at nk.ca
Tue Nov 5 04:37:31 CET 2002


Math-funners, Seq-fans:

One of the best methods for testing whether a number is prime, is the
strong-pseudoprime test. The test is computationally quick, and discerns
a composite number at least three times out of four. Further, one can
perform multiple, independent tests on a number. If N such tests are
performed on a composite number, the probability that it passes each
time is no greater than 1/4^N.

That vanishing probability is not proof. However, if one knows the least
composite number which passes a particular set of tests, then that set
of tests constitutes a primality proof for all smaller numbers.

For example, since we know that all composite numbers below
341550071728321 are exposed by a "witness" among the first seven primes,
one can easily check primality of smaller numbers.

Such values are a Sloane-sequence, A006945. That bound is the seventh
value (hence seven primes), and the eighth value happens to be the same.

Dr. Gerhard Jaeschke discovered that bound in the 1990s, using equipment
of the 1980s. One can hardly find a computer of such sloth nowadays: it
may be that the search for the ninth value is within grasp.
But the ninth may be substantially harder than the seventh. No doubt one
needs either a modern supercomputer, or a distributed effort.

Can I evoke interest in that search?

Oh, but first: does anyone know of such an effort, since Jaeschke's?

--
Don Reble       djr at nk.ca






More information about the SeqFan mailing list