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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there a way to show that $\sqrt{p_{n}} < n$?

In this article, I show that $f_{2}(x)=\frac{x}{ln(x)} - \sqrt{x}$ is ascending, for $\forall x\geq e^{2}$. As a result, $\forall n \geq 3$ $$\frac{p_{n}}{ln(p_{n})} - \sqrt{p_{n}}\leq \frac{p_{n+1}}{ln(p_{n+1})} - \sqrt{p_{n+1}}$$ Also (and as a result), $\forall n \geq 3$ $$ \frac{p_{n}}{ln(p_{n})} - \sqrt{p_{n}} > 0$$ Or $$ \frac{\pi (p_{n})}{p_{n}/ln(p_{n})} < \frac{\pi (p_{n})}{\sqrt{p_{n}}}$$

According to PNT $$\displaystyle\smash{\lim_{n \to \infty }}\frac{\pi (p_{n})}{p_{n}/ln(p_{n})}=1$$ Or, $\forall \varepsilon >0$, $\exists N(\varepsilon )$: $\forall n>N(\varepsilon )$ $$1- \varepsilon < \frac{\pi (p_{n})}{p_{n}/ln(p_{n})} < 1+ \varepsilon$$ Or $$1- \varepsilon < \frac{\pi (p_{n})}{p_{n}/ln(p_{n})} < \frac{\pi (p_{n})}{\sqrt{p_{n}}}$$ As a result $\forall \varepsilon >0$, $\exists N(\varepsilon )$: $\forall n>N(\varepsilon )$ $$(1 - \varepsilon ) \cdot \sqrt{p_{n}} < \pi (p_{n}) = n$$

But this is not enough.

Interestingly, Andrica's conjecture is true iff function $f_{4}(x)=\pi (x) - \sqrt{x}$ is strictly ascending ($x < y \Rightarrow f(x) < f(y)$) for prime arguments.

If $f_{4}(p_{n}) < f_{4}(p_{n+1})$ then $$\pi (p_{n}) - \sqrt{p_{n}} < \pi (p_{n+1}) - \sqrt{p_{n+1}}$$ Or $$\sqrt{p_{n+1}} - \sqrt{p_{n}} < \pi (p_{n+1}) - \pi (p_{n}) =1$$

And vice-versa, if $$\sqrt{p_{n+1}} - \sqrt{p_{n}} < 1$$ Then $$-\sqrt{p_{n}} < -\sqrt{p_{n+1}} + 1$$ Or $$\pi (p_{n})-\sqrt{p_{n}} < \pi (p_{n}) + 1 -\sqrt{p_{n+1}} = \pi (p_{n+1}) -\sqrt{p_{n+1}}$$

So, if Andrica's conjecture is true then $\forall n \geq 3$ $$\pi (p_{n})-\sqrt{p_{n}} > 0$$ Or $$\sqrt{p_{n}} < \pi (p_{n})= n$$

share|cite|improve this question
Even relatively crude bounds on $\pi(x)$, such as $\pi(x)\gt \frac{x}{\log x}$ are enough. Or are you looking for an elementary argument? – André Nicolas Oct 3 '12 at 22:43
up vote 3 down vote accepted

The following upper bound for $p_{n}$ holds for $n\ge 6$: $$ \frac{p_{n}}{n} < \ln n + \ln \ln n=\ln(n\ln n) < n, $$ so $p_n < n^2$ in those cases. It clearly also holds for $p_2=3<4$, $p_3=5<9$, $p_4=7<16$, and $p_5=11<25$ (though it fails for $p_1=2\not<1$).

share|cite|improve this answer
Nice ... I have missed this part… – rtybase Oct 3 '12 at 23:12

This follows from Rosser's result that except at the beginning, $$\pi(x)\gt \frac{x}{\log x}.$$ Just put $x=p_n$. We need to do hand calculation until $\log x>\sqrt{x}$, which happens early.

Remark: We used Rosser's not so easy result only for convenience. The lower bound on $\pi(x)$ obtained by Chebyshev in the middle of the $19$th century, using an "elementary" argument, is already enough.

share|cite|improve this answer
I've missed this too…, the Vallée-Poussin proof's ... so, basically $\pi (x) > \frac{x}{ln(x) - (1-\varepsilon )} > \frac{x}{ln(x)} > \sqrt{x}$ from some $x$ onwards – rtybase Oct 3 '12 at 23:21

Your Answer


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.