I am interested in a proof that for all $n \in \mathbb{N}$ (with just a few exceptions) there will always be a prime $p$ such that $\frac{n}{3} \lt p \le \frac{n}{2}$. Note that the exact boundaries are important (i.e. we don't allow $\frac{n}{3}$). This seems to be true for all $n \gt 3$ except $n=9$ and $n=21$. Does anyone know how to prove this? I found this paper, showing that there is always a prime in the interval $[2n,3n]$, I'm not sure if there is a way to use that. I was able to prove easily that there will always be a prime with $\frac{n}{2} \lt p \le n$ for all $n \gt 2$ with Bertrand's Postulate. Any ideas?

EDIT: I have found a way to prove it, see the accepted answer below.

For anyone who is interested in this intermediate result, I will leave this here:

I can prove the statement for all numbers that are not of the form $6k+3, k \in \mathbb{N}$. For $n=6k$ it follows directly from the paper showing there is always a prime in the interval $[2k,3k]$. Since $2k$ and $3k$ are clearly not prime for $k>1$, we can exclude them as well (in fact, we are already excluding $2k$ in the case $n=6k$). So if we choose $n_1=6k+1$ and $n_2 = 6k+2$ we get that $$]\frac{n_1}{3},\frac{n_1}{2}] \cap \mathbb{N} = ]\frac{n}{3},\frac{n}{2}] \cap \mathbb{N} \subseteq ]\frac{n_2}{3},\frac{n_2}{2}] \cap \mathbb{N},$$

meaning we have at least the same numbers and therefore there is still a prime $p$ with $\frac{n}{3}\lt p \le \frac{n}{2}$. The same is true for $n_{-1}=6k-1$ and $n_{-2}=6k-2$, where the lower bound goes down, so we certainly don't exclude any numbers on that side and the upper bound goes down only enough to exclude $\frac{n}{2}=3k$, which isn't a prime for $k>1$. This argument doesn't work for $n = 6k \pm 3$.

  • 2
    $\begingroup$ We could assume that the boundary values are integers, i.e. $6\mid n$, then writing $n=6k$ gives primes between $2k$ and $3k$. This is proved there. $\endgroup$ – Dietrich Burde Jun 3 '20 at 12:03
  • $\begingroup$ yes, I recognized that too, but I need the proof to hold for all $n \in \mathbb{N}$, not just multiples of 6. In fact I just realized it also follows for numbers of the form $n = 6k+1$ and $n = 6k+2$, since in these cases the lower bound is $2k+\frac{1}{3}$ or $2k+\frac{2}{3}$, so all integers in the interval $[2k,3k]$ are included in the respective intervals as well. (Note that the exceptions mentioned above, 9 and 21, are both of the form $6k+3$) $\endgroup$ – user5615895 Jun 3 '20 at 12:11
  • 1
    $\begingroup$ There are stronger forms of Bertrand, certainly strong enough for your purposes. See this $\endgroup$ – lulu Jun 3 '20 at 12:28
  • $\begingroup$ @lulu I don't see how that helps me. Applying Sylvester's Theorem tells me the $\frac{n}{6}$ (more or less, up to rounding errors) integers between $\frac{n}{3}$ and $\frac{n}{2}$ have a prime factor $\gt \frac{n}{6}$. But that doesn't imply that I have a prime there, I could for example have the integer $\frac{2n}{5}$ in that range with $\frac{n}{5}$ being that prime factor. $\endgroup$ – user5615895 Jun 3 '20 at 16:34
  • 1
    $\begingroup$ Dusart's result, cited in that link, tells us that for sufficiently large $x$ there is always a prime between $x$ and $\left(1+\frac 1{(\ln x)^3}\right)x$. That is considerably better than the factor of $1.5$ which you need. $\endgroup$ – lulu Jun 3 '20 at 18:59

This paper claims to prove that there is a prime in $[3n, 4n]$ for all positive integers $n$. That should suffice for your purposes (for sufficiently large $n$).

Of course you could also take your favourite explicit version of the prime number theorem, but that requires a bit more work.

Edit: Let us complete the argument. Take $n$ sufficiently large (how large we will determine at the end). Now take the smallest integer $k$ so that $3k > \frac n 3$. Note that $3k$ is at most $3$ larger than $\frac n3$. By the theorem I quoted above, there is a prime in $[3k, 4k]$. Since $3k \leq \frac n3 + 3$, we have that $4k \leq \frac 49 n + 4$. Now if we take $n \geq 100$ (say) we have that $\frac 49 n + 3 = \frac 12 n + 3 - \frac{1}{18}n < \frac12 n$. Thus the prime that is in the interval $[3k, 4k]$ is also in the interval $\left(\frac n3, \frac n2\right]$.

  • $\begingroup$ Can you explain how that allows me to conclude there must be a prime between $\frac{n}{3}$ and $\frac{n}{2}$? I don't see it. $\endgroup$ – user5615895 Jun 3 '20 at 18:16
  • $\begingroup$ @user5615895, I've explicitly completed the argument. $\endgroup$ – Mees de Vries Jun 4 '20 at 9:33

lulu pointed me to a certain part of the Wikipedia page on Bertrand's Postulate, where I found this beauty, where the last Theorem (p. 180) tells us that we can always find a prime $p$, such that for any $x\ge8$ we have $$8 \le x \lt p \lt \frac{3x}{2}$$

So if we have $n\ge24$, then $\frac{n}{3}\ge8$ and the above formula tells us there is a prime $p$ with $8 \le \frac{n}{3} \lt p \lt \frac{3}{2}\cdot\frac{n}{3}=\frac{n}{2}$.

Thanks for everyone who helped.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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