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.
Approximating prime number function
-
0@WillJagy: in pari it should be li(x)= - eint1(-log(x)) because of the difference of definition between Ei and E1 [SE link](http://math.stackexchange.com/questions/101114/area-of-validity-of-writing-an-exponential-integral-as-sum-of-integralsinus-and/101126#101126) : Ei(z)=-E1(-z) to simplify... Cheers, – 2012-07-26
5 Answers
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}$
-
0I evaluated it with SAGE and no, it didn't take 6 months. I've put the answer in a comment and now I put it directly in the answer. – 2012-07-26
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.
-
0Yes, Will Jagy linked to that asymptotic expansion in his answer. – 2012-02-25
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
.................................................... 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.
-
0@Gerry, forgot the at sign. I put in a link to the asymptotic expansion. However, I think the OP is more of a one-word-command kind of mathematical software user. – 2012-02-23
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}$
-
1Of course, Schoenfeld's estimate is useless unless you have $Li(N)$ to something over 6,000,000 significant figures. Which you don't. – 2012-02-24