Pomerance in fact outlined how to find a failure example but the computation he suggested was too large for anybody so far to run to completion.
If we're thinking of the same thing -- the "$620 prime" list at https://oeis.org/A018188 -- it's not a question of so far, it's too big to ever be run to completion. There are 2^2030 subsets (2^2030 - 2031 yielding composites) which is a lot more than the number of attoseconds from the Big Bang to the heat death of the universe. Charles Greathouse Analyst/Programmer Case Western Reserve University On Mon, Jun 2, 2014 at 1:20 PM, Warren D Smith <warren.wds@gmail.com> wrote:
RWG: Well this all certainly looks handy, but at the moment I was just looking at how concisely the first "few" primes can be specified, mathematically or algorithmically. I guess I need to stipulate that it shouldn't slow down much with increasing primes.
WDS; Oh. Well, there is actually a spectrum of answers to that question. I mean, at one end, you can specify all the primes via a short definition of what it means to be prime -- O(1) bits, but that is slow. On other end, you can tabulate all primes up to N, very non-concise (N bits), but very fast. If we specify a pseudoprime test and then merely tabulate pseudoprimes up to N, we can get much smaller storage needs and still the time is polynomial in logN. However, known estimates for how many pseudoprimes there are up to N, indicate that your storage needs will still exceed N^0.9999 bits eventually, so this ultimately is not a big win. The AKS primality test has no exceptions.
Pomerance et al 1980 invented a pseudoprime test which later was shown to have no failures for 64-bit integers -- although using Erdosian reasoning it is likely it has an infinite number of failures eventually. Pomerance in fact outlined how to find a failure example but the computation he suggested was too large for anybody so far to run to completion. http://www.pseudoprime.com/dopo.pdf
But nobody has ever found any failure in spite of a money prize and 34 years. My test which also never fails for 64-bit integers has the same conjectured behavior, but is faster than, the Pomerance et al test.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun