0
$\begingroup$

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.

  • 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 5

0

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}$

  • 0
    I 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
3

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.

  • 0
    Yes, Will Jagy linked to that asymptotic expansion in his answer.2012-02-25
1

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.

  • 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
1

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}$

  • 1
    Of 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