For fixed $n > 0$, does there always exist a prime $p$ such that $p < 2^n \leq \lceil p + \sqrt{p} \rceil$? Would this follow from any known conjectures?

This follows immediately from Opperman's conjecture in case $n$ is even. Indeed, in this case $2^n$ is a perfect square, and Opperman's conjecture shows that there's some prime $p$ such that $2^n - 2^{\frac{n}{2}} < p \leq 2^n$. For any such $p$, $p + \sqrt{p} > (2^n - 2^{\frac{n}{2}}) + \sqrt{2^n - 2^{\frac{n}{2}}}$, which falls short of $2^n$ by a real number which converges to 0.5 as $n \rightarrow \infty$ (see this question).

Yet for odd $n$ this seems harder to prove. The best Opperman's conjecture can tell us in this case is that there's a prime $$\lfloor \sqrt{2^n} \rfloor^2 < p \leq \lfloor \sqrt{2^n} \rfloor \cdot \lceil \sqrt{2^n} \rceil < 2^n$$ in case $\lfloor \sqrt{2^n} \rfloor \cdot \lceil \sqrt{2^n} \rceil < 2^n$, or else $$\left( \lfloor \sqrt{2^n} \rfloor - 1 \right) \cdot \lfloor \sqrt{2^n} \rceil < p \leq \lfloor \sqrt{2^n} \rfloor^2 < 2^n$$ in the opposite case $2^n < \lfloor \sqrt{2^n} \rfloor \cdot \lceil \sqrt{2^n} \rceil$ (equality can't be achieved, or else $2^n$ would have two factors which differ by 1).

But for such $p$, the resulting quantity $p + \sqrt{p}$ can still fall short of $2^n$ by an unbounded amount as $n \rightarrow \infty$, and thus fails to give the desired result. Help? Thanks.

  • 2
    $\begingroup$ Certainly Cramer's conjecture would give this, not just for $2^n$ but for any sufficiently large number. $\endgroup$ Dec 15, 2020 at 19:20
  • $\begingroup$ Legendre comes to mind, you can restate it as as there's no prime gap greater than $4 \cdot \lfloor \sqrt{m}\rfloor + 4$ for all $m$ because setting this to $n^2$ we will arrive at $(n+2)^2$ $\endgroup$ Mar 21, 2021 at 14:20


You must log in to answer this question.

Browse other questions tagged .