- 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 - Hello Peter,

> Recently, I've heard on one lecture about an asymptotic approximation of

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

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

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] > > the next coefficient equals to 4!, then 5! and so on, because for x>1

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

> >

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

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.

> >

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

Best,

Andrey

[Non-text portions of this message have been removed]- --- Andrey Kulsha <Andrey_601@...> wrote:
> Hello Peter,

How does that behave as N->+oo ?

>

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

I don't like the "k!"s growing faster than the "(lnx)^k"s

> and

I hope not.

>

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

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 - On Fri, 4 Oct 2002, Peter Kosinar wrote:
> Recently, I've heard on one lecture about an asymptotic approximation of

The expression you give is the asymptotic expansion for

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

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

That is just a cruder approximation to the above integrals.

> form x/(ln x-1)

> by expanding up to O(n/ln^5(n)) {my result was n/ln(n) [1 + 1/ln(n) +

Assuming the Riemann hypothesis

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

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

An asypmtotic expansion only needs to "converge at infinity". The partial

> to 4t-th term, but they definitely can't be equal, because the former

> converges, whereas the other diverges.

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

Integration by parts. Using the first given form of the integral,

> can one calculate it?

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