3 ms·
We can already do this approximately (asymptotically): https://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem "T
by klipt 7y ago
We can already do this approximately (asymptotically): https://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem
"The prime number theorem is equivalent to the statement that the nth prime number p_n satisfies
p_n ~ nlog(n)
the asymptotic notation meaning, again, that the relative error of this approximation approaches 0 as n increases without bound. For example, the 2^1017th prime number is 8512677386048191063, and (2^1017)log(2^1017) rounds to 7967418752291744388, a relative error of about 6.4%."
- eesmith 7y agohttps://www.johndcook.com/blog/2019/06/20/bounds-on-the-nth-prime/ https://www.johndcook.com/blog/2019/06/20/bounds-on-the-nth-... is a recent blog posted titled "Bounds on the nth prime". It lists tighter upper and lower bounds: from math import log def f(n, k): ln = log(n); lln = log(log(n)) return ln + lln - 1 + (lln-2)/ln - ((lln**2) - 6*lln+k)/(2*ln*ln) With that in place, and once I realized that 2^1017 mean 2E17 not 2 to the power of 1017: >>> n = 2E17 >>> lo = n * f(n, 11.847) >>> hi = n * f(n, 10.273) >>> lo 8.512627944213742e+18 >>> hi 8.512727125430618e+18 >>> exact = 8512677386048191063 >>> (exact - lo)/exact 5.80802398678381e-06 >>> (exact - hi)/exact -5.842977499434444e-06