Loading ...
Sorry, an error occurred while loading the content.

best bound

Expand Messages
  • Sebastian Martin
    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
    Message 1 of 11 , Nov 2, 2002
    • 0 Attachment
      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]
    • Andrey Kulsha
      ... Yes, I also believe they exist, but they must be close to R(x). I think the difference is about O[1/log x]. Best, Andrey [Non-text portions of this message
      Message 2 of 11 , Nov 2, 2002
      • 0 Attachment
        Phil Carmody wriote:

        > I believe that there are more accurate functions

        Yes, I also believe they exist, but they must be close to R(x). I think the difference is about O[1/log x].

        Best,

        Andrey


        [Non-text portions of this message have been removed]
      • Andrey Kulsha
        ... Of course, I meant smooth monotonic functions. In fact, pi0(x) = R(x) - sum(R(x^r)) + arctan(pi/logx)/pi - 1/logx, where sum is over non-trivial zeta
        Message 3 of 11 , Nov 2, 2002
        • 0 Attachment
          > Yes, I also believe they exist, but they must be close to R(x). I think the difference is about O[1/log x].

          Of course, I meant smooth monotonic functions. In fact,

          pi0(x) = R(x) - sum(R(x^r)) + arctan(pi/logx)/pi - 1/logx,

          where sum is over non-trivial zeta zeros, and

          pi0(x) = lim(eps->0,(pi(x-eps)+pi(x-eps))/2)

          equals to pi(x) in non-prime points and less than pi(x) by 0.5 in prime points.

          So we can take the sum over some first zeta zeros, e.g. with |r|<=T, and obtain good approximating function with "standard deviation" of about sqrt(2*sum(1/|r|^2)), where sum is over non-taken zeros (with |r|>T in our case). This "standard deviation" comes from the distribution of F(e^u)-pi(e^u) values over positive u's. For R(x) this deviation is about 0.21492188798... (Note that these thoughts are true assuming GSH).

          Best,

          Andrey


          [Non-text portions of this message have been removed]
        • Phil Carmody
          ... 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
          Message 4 of 11 , Nov 2, 2002
          • 0 Attachment
            --- 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/
          • Andrey Kulsha
            ... Please read F(e^u)-pi0(e^u), where F(x) is our approximating function: R(x) + arctan(pi/logx)/pi - 1/logx - sum(R(x^r), some r) ... i.e. when F(x)=R(x)
            Message 5 of 11 , Nov 2, 2002
            • 0 Attachment
              > This "standard deviation" comes from the distribution of F(e^u)-pi(e^u) values over positive u's.

              Please read F(e^u)-pi0(e^u), where F(x) is our approximating function:

              R(x) + arctan(pi/logx)/pi - 1/logx - sum(R(x^r), some r)

              > For R(x) this deviation is about 0.21492188798...

              i.e. when F(x)=R(x) (the term "arctan(pi/logx)/pi - 1/logx" may be omitted since it's O[1/(log x)^3] and tends to zero when x->+inf and doesn't distort the distribution).

              Sorry for so many messages. Good night... |-)

              Andrey


              [Non-text portions of this message have been removed]
            • Andrey Kulsha
              ... Please read (F(e^u)-pi0(e^u))*u*e^(-u/2) of course. Andrey [Non-text portions of this message have been removed]
              Message 6 of 11 , Nov 3, 2002
              • 0 Attachment
                > > This "standard deviation" comes from the distribution of F(e^u)-pi(e^u) values over positive u's.
                >
                > Please read F(e^u)-pi0(e^u), where F(x) is our approximating function:

                Please read (F(e^u)-pi0(e^u))*u*e^(-u/2) of course.

                Andrey


                [Non-text portions of this message have been removed]
              • Andrey Kulsha
                ... http://arxiv.org/abs/math.NT/0210312/ is more correct. Best wishes, Andrey [Non-text portions of this message have been removed]
                Message 7 of 11 , Nov 3, 2002
                • 0 Attachment
                  Sebastian Martín wrote:

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

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

                  Best wishes,

                  Andrey


                  [Non-text portions of this message have been removed]
                • Sebastian Martin
                  Thanks see you: http://arxiv.org/abs/math.NT/0210312 Sincerely Sebastian Martín Ruiz ... _______________________________________________________________
                  Message 8 of 11 , Nov 3, 2002
                  • 0 Attachment
                    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
                  • Phil Carmody
                    ... 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
                    Message 9 of 11 , Nov 3, 2002
                    • 0 Attachment
                      --- 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 ] ]
                      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/
                    • Sebastian Martin
                      ... 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. On the other hand see you this relatively
                      Message 10 of 11 , Nov 4, 2002
                      • 0 Attachment
                        --- Phil Carmody <thefatphil@...> escribió: >
                        --- 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.

                        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
                      • Phil Carmody
                        ... So you agree that the big-Oh expression in the document doesn t apply to the formula in the document? That was my claim. The formula you now allude to is
                        Message 11 of 11 , Nov 4, 2002
                        • 0 Attachment
                          --- Sebastian Martin <sebi_sebi@...> wrote:
                          > --- Phil Carmody <thefatphil@...> escribi�: >
                          > --- 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.

                          So you agree that the big-Oh expression in the document doesn't
                          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
                          > Mathematica program to calculate the prime numbers

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

                          <<<
                          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/
                        Your message has been successfully submitted and would be delivered to recipients shortly.