# Primes between n/3 and n/2

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$$.

• 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. – Dietrich Burde Jun 3 '20 at 12:03
• 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$) – user5615895 Jun 3 '20 at 12:11
• There are stronger forms of Bertrand, certainly strong enough for your purposes. See this – lulu Jun 3 '20 at 12:28
• @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. – user5615895 Jun 3 '20 at 16:34
• 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. – 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]$$.

• 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. – user5615895 Jun 3 '20 at 18:16
• @user5615895, I've explicitly completed the argument. – 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.