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

Approximation for PI(n)

Expand Messages
  • Peter Kosinar
    Hello primehunters, Recently, I ve heard on one lecture about an asymptotic approximation of pi(n) [the number of primes
    Message 1 of 5 , Oct 4, 2002
      Hello primehunters,

      Recently, I've heard on one lecture about an asymptotic approximation of
      pi(n) [the number of primes <=n].

      The given approximation looked like this:
      pi(n) ~ n/ln(n) [1 + 1/ln(n) + 2!/ln^2(n) + 3!/ln^3(n) + O(1/ln^4(n)]

      First, I don't know where did the lector get it from, but as you're lot
      more experienced in the field (not the algebraical meaning :-) ) of
      primes, you might be able to provide me with some reference. When I tried
      to compare this approximation with a similar one obtained form x/(ln
      x-1) by expanding up to O(n/ln^5(n)) {my result was n/ln(n) [1 + 1/ln(n) +
      1/ln^2(n) + 1/ln^3(n) + O(1/ln^4(n)]}, it appears that the former is
      better (although this might be a local trend only).

      Next, the expression in [] strangely resembles SUM(k,1,inf,i!/ln^i(n)) up
      to 4t-th term, but they definitely can't be equal, because the former
      converges, whereas the other diverges. The question is - what is the
      coefficient at 1/ln^4(n) ? Resp. how can one calculate it ?

      Thank you for your time,

      Peter
    • Andrey Kulsha
      Hello Peter, ... the next coefficient equals to 4!, then 5! and so on, because for x 1 Li(x) = x/lnx*(sum(k!/(lnx)^k, k from 1 to N)+O[1/(lnx)^(N+1)]), and
      Message 2 of 5 , Oct 4, 2002
        Hello Peter,

        > Recently, I've heard on one lecture about an asymptotic approximation of
        > pi(n) [the number of primes <=n].
        >
        > The given approximation looked like this:
        > pi(n) ~ n/ln(n) [1 + 1/ln(n) + 2!/ln^2(n) + 3!/ln^3(n) + O(1/ln^4(n)]
        >
        > First, I don't know where did the lector get it from, but as you're lot
        > more experienced in the field (not the algebraical meaning :-) ) of
        > primes, you might be able to provide me with some reference. When I tried
        > to compare this approximation with a similar one obtained form x/(ln
        > x-1) by expanding up to O(n/ln^5(n)) {my result was n/ln(n) [1 + 1/ln(n) +
        > 1/ln^2(n) + 1/ln^3(n) + O(1/ln^4(n)]}, it appears that the former is
        > better (although this might be a local trend only).
        >
        > Next, the expression in [] strangely resembles SUM(k,1,inf,i!/ln^i(n)) up
        > to 4t-th term, but they definitely can't be equal, because the former
        > converges, whereas the other diverges. The question is - what is the
        > coefficient at 1/ln^4(n) ? Resp. how can one calculate it ?

        the next coefficient equals to 4!, then 5! and so on, because for x>1

        Li(x) = x/lnx*(sum(k!/(lnx)^k, k from 1 to N)+O[1/(lnx)^(N+1)]),

        and

        pi(x)-Li(x) = o(1/(lnx)^m) for m as large as you want.

        http://numbers.computation.free.fr/Constants/Primes/countingPrimes.html


        Best wishes,

        Andrey


        [Non-text portions of this message have been removed]
      • Andrey Kulsha
        ... As n- +inf, the series diverges and we should use its generalized sum. ... Oh, I ve meant (pi(x)-Li(x)) = x*o(1/(lnx)^m) for m as large as you want, please
        Message 3 of 5 , Oct 4, 2002
          > > the next coefficient equals to 4!, then 5! and so on, because for x>1
          > >
          > > Li(x) = x/lnx*(sum(k!/(lnx)^k, k from 1 to N)+O[1/(lnx)^(N+1)]),
          >
          > How does that behave as N->+oo ?
          > I don't like the "k!"s growing faster than the "(lnx)^k"s

          As n->+inf, the series diverges and we should use its generalized sum.

          > > and
          > >
          > > pi(x)-Li(x) = o(1/(lnx)^m) for m as large as you want.
          >
          > I hope not.
          > The RHS is o(1). i.e. pi(x) === Li(x) for all x > some fixed X.

          Oh, I've meant (pi(x)-Li(x)) = x*o(1/(lnx)^m) for m as large as you want, please forgive me the typo.

          > > http://numbers.computation.free.fr/Constants/Primes/countingPrimes.html
          >
          > Oh, man, I just love web pages that use 'Ö', 'ó', 'õ', 'æ', 'ú', '£' as if
          > they were HTML.

          :-)

          Best,

          Andrey


          [Non-text portions of this message have been removed]
        • Phil Carmody
          ... How does that behave as N- +oo ? I don t like the k! s growing faster than the (lnx)^k s ... I hope not. The RHS is o(1). i.e. pi(x) === Li(x) for all x
          Message 4 of 5 , Oct 4, 2002
            --- Andrey Kulsha <Andrey_601@...> wrote:
            > Hello Peter,
            >
            > > Recently, I've heard on one lecture about an asymptotic approximation of
            > > pi(n) [the number of primes <=n].
            > >
            > > The given approximation looked like this:
            > > pi(n) ~ n/ln(n) [1 + 1/ln(n) + 2!/ln^2(n) + 3!/ln^3(n) + O(1/ln^4(n)]
            > >
            > > First, I don't know where did the lector get it from, but as you're lot
            > > more experienced in the field (not the algebraical meaning :-) ) of
            > > primes, you might be able to provide me with some reference. When I tried
            > > to compare this approximation with a similar one obtained form x/(ln
            > > x-1) by expanding up to O(n/ln^5(n)) {my result was n/ln(n) [1 + 1/ln(n) +
            > > 1/ln^2(n) + 1/ln^3(n) + O(1/ln^4(n)]}, it appears that the former is
            > > better (although this might be a local trend only).
            > >
            > > Next, the expression in [] strangely resembles SUM(k,1,inf,i!/ln^i(n)) up
            > > to 4t-th term, but they definitely can't be equal, because the former
            > > converges, whereas the other diverges. The question is - what is the
            > > coefficient at 1/ln^4(n) ? Resp. how can one calculate it ?
            >
            > the next coefficient equals to 4!, then 5! and so on, because for x>1
            >
            > Li(x) = x/lnx*(sum(k!/(lnx)^k, k from 1 to N)+O[1/(lnx)^(N+1)]),

            How does that behave as N->+oo ?
            I don't like the "k!"s growing faster than the "(lnx)^k"s

            > and
            >
            > pi(x)-Li(x) = o(1/(lnx)^m) for m as large as you want.

            I hope not.
            The RHS is o(1). i.e. pi(x) === Li(x) for all x > some fixed X.

            > http://numbers.computation.free.fr/Constants/Primes/countingPrimes.html

            Oh, man, I just love web pages that use '�', '�', '�', '�', '�', '�' as if
            they were HTML.


            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!?
            New DSL Internet Access from SBC & Yahoo!
            http://sbc.yahoo.com
          • Carl Devore
            ... The expression you give is the asymptotic expansion for li(n) = Int(1/ln(t), t= 0..n) = Int(exp(t)/t, t= -infinity..ln(n)) where in either integral the
            Message 5 of 5 , Oct 4, 2002
              On Fri, 4 Oct 2002, Peter Kosinar wrote:
              > Recently, I've heard on one lecture about an asymptotic approximation of
              > pi(n) [the number of primes <=n].
              >
              > The given approximation looked like this:
              > pi(n) ~ n/ln(n) [1 + 1/ln(n) + 2!/ln^2(n) + 3!/ln^3(n) + O(1/ln^4(n)]
              >
              > First, I don't know where did the lector get it from....

              The expression you give is the asymptotic expansion for
              li(n) = Int(1/ln(t), t= 0..n) = Int(exp(t)/t, t= -infinity..ln(n))
              where in either integral the principal value is taken to integrate over
              the singularities at 1 and 0 respectively. (In some texts the above
              integral is named li_0(n), and li(n) is used for the integral from 2 to n.
              It only amounts to a constant difference of about 1.05.)

              > When I tried to compare this approximation with a similar one obtained
              > form x/(ln x-1)

              That is just a cruder approximation to the above integrals.

              > by expanding up to O(n/ln^5(n)) {my result was n/ln(n) [1 + 1/ln(n) +
              > 1/ln^2(n) + 1/ln^3(n) + O(1/ln^4(n)]}, it appears that the former is
              > better (although this might be a local trend only).

              Assuming the Riemann hypothesis
              abs(pi(x)-li(x)) < 1/8/Pi*sqrt(x)*ln(x).
              So it is a good approximation.

              > Next, the expression in [] strangely resembles SUM(k,1,inf,i!/ln^i(n)) up
              > to 4t-th term, but they definitely can't be equal, because the former
              > converges, whereas the other diverges.

              An asypmtotic expansion only needs to "converge at infinity". The partial
              ums of the series give finer and finer approximations even though the
              series diverges for any finite n.

              > The question is - what is the coefficient at 1/ln^4(n) ? Resp. how
              > can one calculate it?

              Integration by parts. Using the first given form of the integral,
              repeatedly integrate by parts, letting u be the whole integrand.

              All of this is covered in _Prime Numbers: A Computational Perspective_ by
              Richard Crandall and Carl Pomerance (Springer, 2001).
            Your message has been successfully submitted and would be delivered to recipients shortly.