0
$\begingroup$

According to the prime number theorem there are about $n/\ln(n)$ primes less than $n$. This value is a limit but it could fluctuate. My question is, is there a known bound on this fluctuation? i.e. are there functions $f$ and $g$ such that $\forall n>100, f(n) < \mathrm{numPrimes}(n) \lt g(n)$? How tight is this bound? Could there be an $n$ for which the number of primes less than $n$ is smaller than $n/\sqrt{n}$? Could there be an $n$ for which there are more than $n/2$ (for $n\gt 100$ let's say) primes less than $n$?

Trivially $0 \lt\mathrm{numPrimes}(n) \lt n$, how tight a bound has been achieved?

$\endgroup$

2 Answers 2

6
$\begingroup$

Let $\pi(x)$ denote the prime counting function. Pierre Dusart has shown that $$\pi(x) \geq \frac{x}{\log(x)-1} \qquad \qquad \mbox{ for }x\geq 5393$$ and $$\pi(x) \leq \frac{x}{\log(x)-1.1}\qquad \qquad \mbox{ for } x\geq 60184.$$

Many other results of a similar flavor are also shown in this paper.

$\endgroup$
0
0
$\begingroup$

I have understood it to be an asymptotic expression, i.e. $$ \pi(x)\sim \frac{x}{\log x-1} $$ for large $x$. That is to say, for any positive functions $f(x)>0$ and $g(x)>0$ there exists an $n$ such that $$ \frac{x}{\log x-1}-f(x)<\pi(x)<\frac{x}{\log x-1}+g(x). $$ for all $x>n$.

$\endgroup$
1
  • 1
    $\begingroup$ I believe that the point of the question is to be able to give (explicit) functions f(x) and g(x) for which you can actually say what n is. $\endgroup$
    – user1073
    Jun 7, 2015 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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