MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

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




  • Prev by Date: RE: RE: Notebook for Primes
  • Next by Date: Re: Re: Reading/Writing files across networks
  • Previous by thread: RE: RE: Notebook for Primes
  • Next by thread: Re: Re: RE: Notebook for Primes