- Hi all:

¿which is the best bound for the prime counting

function

Pi(x), please?

Is to improve the program attached for obtain prime

numbers

Sincerely

Sebastián

_______________________________________________________________

Yahoo! Messenger

Nueva versión: Webcam, voz, y mucho más ¡Gratis!

Descárgalo ya desde http://messenger.yahoo.es

[Non-text portions of this message have been removed] - --- Sebastian Martin <sebi_sebi@...> wrote:
> --- Phil Carmody <thefatphil@...> escribi�: >

So you agree that the big-Oh expression in the document doesn't

> --- Sebastian Martin <sebi_sebi@...> wrote:

> > > Thanks

> > >

> > > see you:

> > >

> > > http://arxiv.org/abs/math.NT/0210312

> >

> > Sorry, but you're never going to persuade the person

> > who made Bernstien's

> > primegen twice as fast to move to a claimed

> > O(n^(3/2)) time algorithm.

> >

> > You do know that O(n^(3/2)) is no faster than just

> > testing each number in

> > turn using _nothing but trial division_, don't you?

> > (Which is basically a

> > subset of what's taking place in the algorithm

> > described therein.)

> >

> > I'd be curious to see the proof that expresion (7)

> > is O(n^(3/2)), because

> > it's basically

> > pi(x) = Sum { j=2..x } [ expression1 involving Sum

> > { i=1..j } [ expresson2 ] ]

>

> You can make the sum of d(i) only to Sqrt[i]

> and multiplied by 2 in F(n), the perfect square

> are not problem.

apply to the formula in the document? That was my claim.

The formula you now allude to is now effectively trial dividing every

number, including all composites, to its square root in order to see

if it's prime, with _no_ early abort if you find a factor.

This is still crazier than the trial-division method with an instant abort,

which is still slower than any other method sensibly proposed in the last

200 years.

> On the other hand see you this relatively fast

No I don't. I see an _incredibly slow_ Mathematica program.

> Mathematica program to calculate the prime numbers

<<<

In[9]:= p=100000

Out[9]= 100000

In[10]:= While[p < 100100,

{n = Floor[N[1.045 + NIntegrate[1/Log[x], {x, 2, p}], 15]];

A = Floor[(n + 1)*Log[n + 1] + (n + 1)*(Log[Log[n+ 1]] - 0.9385)];

T = G[A]; m = A - 1; B = Timing[While[m > p, (T =(T + 1)*G[m]; m--)]];

k = p; p = p + 1 + T;

Print["NXT(", k, ")=", p, " ", PrimeQ[p], " ",B]}]

NXT(100000)=100003 True {1.42 Second, Null}

NXT(100003)=100019 True {1.33 Second, Null}

NXT(100019)=100043 True {1.32 Second, Null}

NXT(100043)=100049 True {1.32 Second, Null}

Interrupt> a

Out[10]= $Aborted

In[11]:= p=1000000

Out[11]= 1000000

In[12]:= While[p < 1000100,

{n = Floor[N[1.045 + NIntegrate[1/Log[x], {x, 2, p}], 15]];

A = Floor[(n + 1)*Log[n + 1] + (n + 1)*(Log[Log[n+ 1]] - 0.9385)];

T = G[A]; m = A - 1; B = Timing[While[m > p, (T =(T + 1)*G[m]; m--)]];

k = p; p = p + 1 + T;

Print["NXT(", k, ")=", p, " ", PrimeQ[p], " ",B]}]

NXT(1000000)=1000003 True {19.01 Second, Null}

NXT(1000003)=1000033 True {18.96 Second, Null}

NXT(1000003)=1000033 True {18.96 Second, Null}

NXT(1000033)=1000037 True {18.94 Second, Null}>>>

Notice the time of day in the following Pari/GP prompts, and the size of the

arguments I'm giving it.

<<<

(15:35) gp > isprime(nextprime(10^200))

%17 = 1

(15:35) gp > isprime(nextprime(10^210))

%18 = 1

(15:35) gp > isprime(nextprime(10^220))

%19 = 1

(15:35) gp > isprime(nextprime(10^230))

%20 = 1

(15:35) gp > isprime(nextprime(10^240))

%21 = 1

(15:36) gp > isprime(nextprime(10^250))

%22 = 1

(15:36) gp > isprime(nextprime(10^260))

%23 = 1

(15:36) gp > isprime(nextprime(10^270))

%24 = 1

(15:36) gp > isprime(nextprime(10^280))

%25 = 1

(15:36) gp > isprime(nextprime(10^290))

%26 = 1>>>

To suggest that the Mathematica program is a fast program is the same

as suggesting that everyone should be using Turing Machines for speed.

I don't buy it, personally.

Phil

=====

First rule of Factor Club - you do not talk about Factor Club.

Second rule of Factor Club - you DO NOT talk about Factor Club.

Third rule of Factor Club - when the cofactor is prime, or you've trial-

divided up to the square root of the number, the factoring is over.

__________________________________________________

Do you Yahoo!?

HotJobs - Search new jobs daily now

http://hotjobs.yahoo.com/