Approximating prime number function

Question

What is the best way to approximate how many primes there are less than $2^{43112609}-1$? I know that one can use prime number theorem. I also found that in the Internet that $\pi (10^{24})=18435599767349200867866$ and then one can use Loo's theorem that there are always prime between $3n$ and $4n$ so this method gives an upper and a lower bound.

Answer 1

Follow JavaMan's hint: (logarithmic integral)

$$\pi (n) \sim \int _{ 2 }^{ n }{ \frac{1}{\log{\quad x}}}dx$$

It is aproximately: $1.0590175682245865561220555017659840985462778602424400915*{10}^{12978181}$

Answer 2

We can compute the Logarithmic Integral, as suggested by JavaMan, with $$ \begin{align} \operatorname{li}(x) &=\operatorname{PV}\int_0^x\frac{\mathrm{d}t}{\log(t)}\\ &=\gamma+\log|\log(x)|+\sum_{k=1}^\infty\frac{\log(x)^k}{k\;k!} \end{align} $$ which converges for all $x>0$.

For large values of x, there is an asymptotic expansion: $$ \operatorname{li}(x)=\frac{x}{\log(x)}\left(1+\frac{1}{\log(x)}+\frac{2}{\log(x)^2}+\dots+\frac{k!}{\log(x)^k}+O\left(\frac{1}{\log(x)^{k+1}}\right)\right) $$ This doesn't converge, as is the case with most asymptotic expansions.

Answer 3

It turns out SAGE does not have a single function name for the logarithmic integral, but that is not necessary. It does have the exponential integral. In Abramowitz and Stegun this is written $\mbox{Ei}(x),$ see formula 5.1.2 on page 228. Meanwhile, formula 5.1.3 on the same page gives what you want $$ \mbox{li}(x) = \mbox{Ei}(\log x), $$ where logarithms are base $e = 2.718281828459...$ So that is what you want. In SAGE, I found

http://www.sagemath.org/doc/reference/sage/rings/real_mpfr.html?highlight=erfc#sage.rings.real_mpfr.RealNumber.erfc

....................................................

eint()

    Returns the exponential integral of this number.

    EXAMPLES:

    sage: r = 1.0
    sage: r.eint()
    1.89511781635594

    sage: r = -1.0
    sage: r.eint()
    NaN

...................................................

log(base='e')

    EXAMPLES:

    sage: R = RealField()
    sage: R(2).log()
    0.693147180559945
    sage: log(RR(2))
    0.693147180559945
    sage: log(RR(2),e)
    0.693147180559945

    sage: r = R(-1); r.log()
    3.14159265358979*I
    sage: log(RR(-1),e)
    3.14159265358979*I
    sage: r.log(2)
    4.53236014182719*I

......................................................... 

So, however SAGE syntax works, you want eint(log x)) for your number...

For comparison, $$ \mbox{li}(2) = 1.04516378..., $$ $$ \mbox{li}(e) = 1.895117816... $$

and you can compare some other small values with robjohn's formula until you are sure you have it right.

As Gerry points out, this is still unlikely to give a value, So, the best you can do is the asymptotic series, I expect the best accuracy is taking $n$ terms when $n \approx \log x,$ which is still huge but actually possible to calculate with a loop and patience. That is, take about $43,112,609 \log 2 \approx 29,883,383 $ terms. If you run out of patience, just do 100 terms. Or ten.

Answer 4

Maple says:

N:= 2^(43112609)-1: evalf(Li(N));

$0.1059014049\ 10^{12978182}$

Assuming the Riemann hypothesis, Schoenfeld's estimate says the error $|\pi(N) - \text{li}(N)| \le\sqrt{N} \log(N)/(8 \pi) = 0.2115223997\ 10^{6489101}$