RE: RE: Notebook for Primes
- To: mathgroup at smc.vnet.net
- Subject: [mg36046] RE: [mg36023] RE: [mg35992] Notebook for Primes
- From: "DrBob" <majort at cox-internet.com>
- Date: Wed, 14 Aug 2002 05:35:14 -0400 (EDT)
- Reply-to: <drbob at bigfoot.com>
- Sender: owner-wri-mathgroup at wolfram.com
By the way, Mathematica gets the following limit wrong: f[n_] := Log[n]^Log[Log[n]] Limit[f[n]/n, n -> Infinity] Infinity That limit is zero. For the Sieve to be polynomial, we only need the sequence to be BOUNDED (for some power of n in the denominator). Bobby Treat -----Original Message----- From: DrBob [mailto:majort at cox-internet.com] To: mathgroup at smc.vnet.net Subject: [mg36046] RE: [mg36023] RE: [mg35992] Notebook for Primes What makes you think log(n)^(log log(n)) isn't dominated by a polynomial? Actually, it is, and the Sieve of Eratosthenes is polynomial just like I said. For instance, n^k dominates, for ANY k>0 (including 1): f[n_] := Log[n]^Log[Log[n]] Plot[{f[n]/Sqrt[n]}, {n, 1, 100000}] logF[n_] := Log[Log[n]]^2 Limit[logF[n]/Log[n], n -> Infinity] In my initial testing, the Sieve is far faster than the new algorithm, too. FAR faster. Bobby -----Original Message----- From: dterr at wolfram.com [mailto:dterr at wolfram.com] To: mathgroup at smc.vnet.net Subject: [mg36046] Re: [mg36023] RE: [mg35992] Notebook for Primes DrBob wrote: > The oldest algorithm for testing primes... the Sieve of Eratosthenes... > is polynomial and deterministic. It's simply too slow to use, just like > the one at the attachment. > > Bobby Actually that's not true. The Sieve of Eratosthenes has complexity log(n)^(log log(n)). The algorithm below is the first deterministic primality test known to be polynomial. Unfortunately, it still appears to be not practical. David > -----Original Message----- > From: Jeff Dillon [mailto:jeffdi at fidalgo.net] To: mathgroup at smc.vnet.net > Subject: [mg36046] [mg36023] [mg35992] Notebook for Primes > > Is there a publicly available Mathematica 3.0 notebook that implements > the Primes is in P? > > http://www.msnbc.com/news/792126.asp