# Approximating prime number function

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.

-
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

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

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

-
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
@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

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.

-
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

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.

-
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

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

-
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