I was wondering if someone could possibly help me verify the following:
For sufficiently large $n$ there is always a prime between $n- \sqrt{n}$ and $n$.
I am not sure if this is true or not. If it is true could you possibly explain me how the Prime number theorem is applied to get the answer?
$\endgroup$2 Answers
$\begingroup$I do not think you will have an easy time proving this result. There are a number of reasons for this. First, the Legendre conjecture states that there is at least one prime between $n^2$ and $(n+1)^2$, an interval of length that is order of $n$. As far as I know this is still unsolved. If we rescale your problem, we get that you want to show there are primes between $n^2-n$ and $n^2$ for $n$ large enough. Notice that $(n-1)^2=n^2-2n+1<n^2-n$. So if you could show your statement to be true, then you will have proven the Legendre conjecture for large enough $n$, and if you could produce a good lower bound on $n$ then a computer search will likely prove the Legendre conjecture.
The prime number theorem says $\pi(n)=O(n/\log(n))$. In fact the limit of the ratio is 1. So for all $0<C<1$, there exists a $N_c$, such that for all $n\geq N_c$,
$$c\leq \frac{\pi(n)}{n/\log(n)}$$
The interval you have is of length $\sqrt{n}$. In fact, the interval $[1,n]$ can be broken into $[1,n-\sqrt{n}]$ and $[n-\sqrt{n},n]$. In other words, you could try showing that there are at least $n-\sqrt{n}$ primes. No matter what $c$ you chose in the above, you will not attain a density this high for all large $n$.
You also might be interested in the Oppermann Conjecture which is a somewhat stronger version of your problem.
$\endgroup$ 3 $\begingroup$Your question is the lower part of Oppermann's conjecture that I think to have proved in a publication available at: and for which I still wait some commentaries. The title of this article is 'From Sierpinski's conjecture to Legendre'. It has been published in the journal Theoretical Mathematics & Applications, vol.4, no.2, 2014, 65-77, ISSN: 1792-9687 (print), 1792-9709 (online) Scienpress Ltd, 2014. In this article, I show that Sierpinski's, Oppermann's and Legendre's conjectures (see Wikipedia for definitions), all dealing with N², can be integrated into a new global D conjecture which possesses a property of recurrence.This property is used to prove these three linked conjectures respecting the order: Oppermann's first and conditional to D, Sierpinski's second and conditional to D, D third and unconditional, Oppermann's and Sierpinski's fourth and unconditional, and finally Legendre's. Regards.
$\endgroup$ 1
