Are $14$ and $21$ the only "interesting" numbers?

Solution 1:

Note that exactly one of $n$ and $n+1$ is even. It follows that for $n$ to be interesting, either $n=3p$ and $n+1=2N(p)$ or $n=2p$ and $n+1=3P(p)$, where $P(p)$ and $N(p)$ are the previous and next primes to $p$ respectively. Rearranging we get that $p$ must satisfy one of the following two equations: $$\frac{3p+1}2=N(p)\tag1$$ $$\frac{2p+1}3=P(p)\tag2$$ However, by a 1952 result of Jitsuro Nagura, for $p\ge25$ there is always a prime between $p$ and $\frac65p$. In particular, if $p\ge31$ is a prime: $$\frac56p<P(p)<p<N(p)<\frac65p$$ But when $p\ge31$ the following inequalities are also true: $$\frac{2p+1}3<\frac56p\qquad\frac65p<\frac{3p+1}2$$ Therefore, if $p$ is to satisfy $(1)$ or $(2)$ above, it must be less than 31. This leaves a handful of cases to check for $p$, and we find that the only interesting numbers are 14 and 21 as conjectured.

The Nagura paper is a reference in the Wikipedia article on Bertrand's postulate. While those in the comments had saw it, sketching out the approach I use here, I already knew what to do; I did not read those comments in detail until after posting my answer.