OFFSET
1,1
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.
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)?
EXAMPLE
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
PROG
(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), ", "))
CROSSREFS
KEYWORD
nonn
AUTHOR
Cino Hilliard, Aug 08 2006, Aug 17 2006
EXTENSIONS
More terms from Hugo Pfoertner, Nov 17 2019
More precise name by Hugo Pfoertner, Apr 29 2021
STATUS
approved