- Sebastian Martín wrote:

> see you:

http://arxiv.org/abs/math.NT/0210312/ is more correct.

>

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

Best wishes,

Andrey

[Non-text portions of this message have been removed] - Thanks

see you:

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

Sincerely

Sebastian Martín Ruiz

--- Phil Carmody <thefatphil@...> escribió: >

--- Sebastian Martin <sebi_sebi@...> wrote:> > 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

>

>

> There are two fairly good approximations that are in

> common use.

> One is just 'li':

>

> li(x) =~ 1.045+ Integral{x = 2 .. +inf} [ x/ln(x) ]

> (the 1.045 is effecively the li(2) component, the

> integral from 0..2)

>

> The second is one of Riemann's, and is a

> modifications to the above

>

> R(x) = Sum {n = 1..+inf} [ mu(n)/n . li(x^(1/n)) ]

>

> mu(n) = the mobius function, which is 0 if n

> contains a repeated factor,

> -1 for n with an odd number of prime factors, and +1

> for n with an even

> number of prime factors. mu({1..7...}) =

> {1,-1,-1,0,-1,+1,-1...}

> so

> R(x) = li(x) - li(x^(1/2))/2 - li(x^(1/3))/3 -

> li(x^(1/5))/5 + li(x^(1/6))/6 - ...

>

> R(x)-pi(x) hovers around zero much more than

> li(x)-pi(x) does, and most of

> the time seems more accurate.

>

> I believe that there are more accurate functions,

> that are computationally

> harder to evaluate, perhaps Mathworld has more

> information.

>

>

> 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/

>

> ------------------------ Yahoo! Groups Sponsor

>

> Unsubscribe by an email to:

> primenumbers-unsubscribe@yahoogroups.com

> The Prime Pages : http://www.primepages.org/

>

>

>

> Your use of Yahoo! Groups is subject to

> http://docs.yahoo.com/info/terms/

>

>

Yahoo! Messenger

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

Descárgalo ya desde http://messenger.yahoo.es - --- Sebastian Martin <sebi_sebi@...> wrote:
> Thanks

Sorry, but you're never going to persuade the person who made Bernstien's

>

> see you:

>

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

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 ] ]

I can enumerate x(x-1)/2-1 evaluations of expression 2. And that's O(x^2).

Please enlighten us how you perform O(x^2) divisions and additions in O(x^(3/2))

time.

You've also completely neglected the asymptotic behaviour of the operations

that you're performing, so you'd need at least an extra epsilon in the

exponent.

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/ - --- Phil Carmody <thefatphil@...> escribió: >

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

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

> >

> > 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 ] ]

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

are not problem.

On the other hand see you this relatively fast

Mathematica program to calculate the prime numbers

based in the second formula of www.primepuzzles.net

Problem 38

(* Formula to Obtain the Next Prime to any Number p >

114 *)

DD[i_] := Sum[Quotient[i, j] - Quotient[i - 1, j], {j,

1, Sqrt[i]}]

G[i_] := -Quotient[2 - 2*DD[i], i]

(* Bound for Pi[p] prime counting function (Exist

other better?)*)

(* Rosser and Schoenfeld inequalities *)

(* Nested Product O(nlogn)^(3/2) *)

p = 114

114

While[p < 1000,

{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]}]

> I can enumerate x(x-1)/2-1 evaluations of expression

_______________________________________________________________

> 2. And that's O(x^2).

> Please enlighten us how you perform O(x^2) divisions

> and additions in O(x^(3/2))

> time.

>

> You've also completely neglected the asymptotic

> behaviour of the operations

> that you're performing, so you'd need at least an

> extra epsilon in the

> exponent.

>

> 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/

>

Yahoo! Messenger

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

Descárgalo ya desde http://messenger.yahoo.es - --- 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/