|
|
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.
|
|
3
|
|
|
29, 536, 7923, 104768, 1299733, 15484040, 179431239, 2038076587, 22801797576, 252097715777, 2760727752353, 29996225393465, 323780512411510, 3475385760290723, 37124508056355511, 394906913798224975, 4185296581676470068, 44211790234127235470
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
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]
|
|
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
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|