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
    Commented Jun 7, 2015 at 1:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .