1,1

The algorithm primex(x) uses an exponent bisection routine and Gram's Riemann approximation, Rg(x) for the prime counting function Pi(x). We know that Rg(x) is relatively close to Pi(x) as x gets large. We take advantage of this relatively small error noting that Pi(prime(x)) = x ~ Rg(prime(x)). A reasonable approximation of prime(x) is xlog(x) while for x = 10^n, often, 10^nlog(10^(n+1) is a much better approximation. The Pari program shows the flow of this algorithm.

Chris Caldwell, The Prime Page.

David Broadhurst, Primeforn yahoo group.

The largest known prime(10^n) = A006988(18) = 44211790234832169331 and a(18) = 44211790234127235470. So the approximation primex(10^18) is accurate to 11 places.

(PARI) primex3(n) = \List the approximations to the (10^n)-th prime \ By Cino hilliard { for(x=1, n, print1(primex(10^x)", ")) } primex(n) = { local(x, px, r1, r2, r, p10, b, e); b=10; p10=log(n)/log(10); if(Rg(b^p10*log(b^(p10+1)))< b^p10, m=p10+1, m=p10); r1 = 0; r2 = 1; for(x=1, 400, r=(r1+r2)/2; px = Rg(b^p10*log(b^(m+r))); if(px <= b^p10, r1=r, r2=r); r=(r1+r2)/2; ); floor(b^p10*log(b^(m+r))+.5); } Rg(x) = \Gram's Riemann's Approx of Pi(x) { local(n=1, L, s=1, r); L=r=log(x); while(s<10^120*r, s=s+r/zeta(n+1)/n; n=n+1; r=r*L/n); (s) }

Cf. A006988.

Adjacent sequences: A121043 A121044 A121045 this_sequence A121047 A121048 A121049

Sequence in context: A028180 A028171 A028146 this_sequence A028168 A028139 A028137

base,nonn,uned

Cino Hilliard (hillcino368(AT)gmail.com), Aug 08 2006, Aug 17 2006