RE: RE: Notebook for Primes
- To: mathgroup at smc.vnet.net
- Subject: [mg36048] RE: [mg36023] RE: [mg35992] Notebook for Primes
- From: "DrBob" <majort at cox-internet.com>
- Date: Wed, 14 Aug 2002 05:35:16 -0400 (EDT)
- Reply-to: <drbob at bigfoot.com>
- Sender: owner-wri-mathgroup at wolfram.com
Oops! I couldn't reproduce that error. Here's a more complete proof
that Log[n]^Log[Log[n]] is bounded by n, and the limit comes out right
(0).
f[n_] := Log[n]^Log[Log[n]]
Plot[{f[n]/n}, {n, 1, 100000}]
logF[n_] := Log[Log[n]]^2
Limit[Log[x]/Sqrt[x], x -> Infinity]
Limit[Log[x]^2/x, x -> Infinity]
Limit[Log[Log[n]]^2/Log[n], n -> Infinity]
Limit[Exp[logF[n]]/n, n -> Infinity]
Simplify[Exp[logF[n]] - f[n]]
Limit[f[n]/n, n -> Infinity]
Bobby
-----Original Message-----
From: DrBob [mailto:majort at cox-internet.com]
To: mathgroup at smc.vnet.net
Subject: [mg36048] RE: [mg36023] RE: [mg35992] Notebook for Primes
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: [mg36048] 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: [mg36048] 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: [mg36048] [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