Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
The logarithmic integral tends to be a tighter approximation than the prime number theorem. –  JavaMan Feb 23 '12 at 19:00
    
@JavaMan Sage has separate eint() and log() functions, see my answer. The OP evidently likes Sage but does not really know how to use it. Mathematica does have a single LogIntegral[z] function. gp-pari has eint1(), so we can combine eint1(log(x)) just as in Sage. –  Will Jagy Feb 23 '12 at 22:22
    
@WillJagy: in pari it should be li(x)= - eint1(-log(x)) because of the difference of definition between Ei and E1 SE link : Ei(z)=-E1(-z) to simplify... Cheers, –  Raymond Manzoni Jul 26 '12 at 17:39
add comment

4 Answers

up vote 0 down vote accepted

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

share|improve this answer
    
Done. Silly error –  dot dot Feb 23 '12 at 19:15
    
I see. However, I was unable to solve my problem as I try it in Sage. N(integrate(1/ln(x),2,10^1000)) says Traceback (click to the left of this block for traceback) ... RuntimeError: Floating point exception –  student Feb 23 '12 at 20:03
    
@student, not the right way to do it... –  Will Jagy Feb 23 '12 at 22:27
2  
@dot, do you have a good way to evaluate that integral when $x$ is on the order of $2^{40,000,000}$? –  Gerry Myerson Feb 23 '12 at 22:43
    
@dotdot did it take 6 months (Feb-Jul) to evaluate the integral? :) But seriously, how did you evaluate it? –  user2468 Jul 26 '12 at 17:41
show 1 more comment

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.

share|improve this answer
1  
How well does this work when $x$ is on the order of $2^{40,000,000}$? –  Gerry Myerson Feb 23 '12 at 22:40
    
@Gerry: I have added an asymptotic expansion. I have proofs of both of these formulas, if there is interest (they are long, but I could work on shortening them a bit). –  robjohn Feb 25 '12 at 4:27
    
Yes, Will Jagy linked to that asymptotic expansion in his answer. –  Gerry Myerson Feb 25 '12 at 4:56
add comment

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.

share|improve this answer
    
Is this practical for $x$ on the order of $2^{40,000,000}$? –  Gerry Myerson Feb 23 '12 at 22:41
    
Gerry, I have no idea. If I thought the OP up to it, I would give enough background and a few terms of the standard asymptotic expansion for $\mbox{li} \; x.$ Screw it, I will find something and type it in. –  Will Jagy Feb 23 '12 at 22:45
    
@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. –  Will Jagy Feb 23 '12 at 22:58
add comment

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

share|improve this answer
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. –  Gerry Myerson Feb 24 '12 at 12:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.