A121046 - OEIS

%I #33 Apr 03 2023 10:36:11

%S 29,536,7923,104768,1299733,15484040,179431239,2038076587,22801797576,

%T 252097715777,2760727752353,29996225393465,323780512411510,

%U 3475385760290723,37124508056355511,394906913798224975,4185296581676470068,44211790234127235470

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

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

%H Hugo Pfoertner, <a href="/A121046/b121046.txt">Table of n, a(n) for n = 1..100</a>

%H Chris Caldwell, <a href="https://t5k.org/">The Prime Page</a>.

%H Cino Hilliard, David Broadhurst, Andrey Kulsha, <a href="/A121046/a121046.txt">Number of prime-index-primes < n</a>, digest of 15 messages in primeform Yahoo group, Apr 2 - Apr 5, 2006. [Cached copy]

%H Mathematics Stack Exchange, <a href="http://math.stackexchange.com/questions/1848854/how-many-digits-of-the-googol-th-prime-can-we-calculate-or-were-calculated">How many digits of the googol-th prime can we calculate (or were calculated)?</a>

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

%e Agrees for 52 digits with the solution to Li(x)=10^100 given in Mathematics Stack Exchange link. - _Hugo Pfoertner_, Nov 17 2019

%o (PARI) \\ List the approximations to the (10^n)-th prime by _Cino Hilliard_

%o \\ Gram's Riemann's Approx of Pi(x)

%o 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) }

%o 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); }

%o for (k=1,20,print1(primex(10^k),", "))

%Y Cf. A006988, A052434, A274767.

%K nonn

%O 1,1

%A _Cino Hilliard_, Aug 08 2006, Aug 17 2006

%E More terms from _Hugo Pfoertner_, Nov 17 2019

%E More precise name by _Hugo Pfoertner_, Apr 29 2021