A121046 Approximation to the (10^n)-th prime by applying a bisection to Gram's formula for Riemann's approximation of the prime counting function.

29, 536, 7923, 104768, 1299733, 15484040, 179431239, 2038076587, 22801797576, 252097715777, 2760727752353, 29996225393465, 323780512411510, 3475385760290723, 37124508056355511, 394906913798224975, 4185296581676470068, 44211790234127235470

Offset: 1

Author

Cino Hilliard, Aug 08 2006, Aug 17 2006

Keywords

• nonn

Comments

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 x*log(x) while for x = 10^n, often, 10^n*log(10^(n+1)) is a much better approximation. The PARI program shows the flow of this algorithm.

Examples

			pi(10^18) = A006988(18) = 44211790234832169331 and a(18) = 44211790234127235470. So the approximation of pi(10^18) by primex(10^18) is accurate to 11 places.
Agrees for 52 digits with the solution to Li(x)=10^100 given in Mathematics Stack Exchange link. - _Hugo Pfoertner_, Nov 17 2019
		

Links

• Hugo Pfoertner, Table of n, a(n) for n = 1..100
• Chris Caldwell, The Prime Page.
• Cino Hilliard, David Broadhurst, Andrey Kulsha, Number of prime-index-primes < n, digest of 15 messages in primeform Yahoo group, Apr 2 - Apr 5, 2006. [Cached copy]
• Mathematics Stack Exchange, How many digits of the googol-th prime can we calculate (or were calculated)?

Crossrefs

Cf. A006988, A052434, A274767.

Programs

PARI

\\ List the approximations to the (10^n)-th prime by Cino Hilliard
\\ Gram's Riemann's Approx of Pi(x)
Rg(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) }
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); }
for (k=1,20,print1(primex(10^k),", "))

Extensions

More terms from Hugo Pfoertner, Nov 17 2019

More precise name by Hugo Pfoertner, Apr 29 2021