## Approximation for PI(n)

Expand Messages
• 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 ?

Peter
• 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]
• ... 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]
• ... 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.

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
• ... 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.