# Is there always a prime $p$ which falls short of $2^n$ by at most a square-root factor?

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.

• Certainly Cramer's conjecture would give this, not just for $2^n$ but for any sufficiently large number. Dec 15, 2020 at 19:20
• 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$ Mar 21, 2021 at 14:20