Big O of the square root of n, or big O of n to the power of one half, is what Legendre's conjecture implies about the upper bound for the prime gap above any natural number n, right?

I have seen it expressed as $O(\sqrt{p})$ but what does the p represent? I think p is used to represent any given prime. Can we use n to represent any given natural number and express it as $O(\sqrt{n})$ because the gap between any n and the next consecutive prime is bounded so, not only the gap between consecutive primes, assuming Legendre's conjecture?

  • $\begingroup$ Let $n$ be any natural number $>1$ and let $p$ be the largest prime not exceeding $n$. Then $\sqrt{p} \le \sqrt{n}$, so if the gap from $p$ to the next prime is $O(\sqrt{p})$ then of course the gap from $n$ to the next prime (which is even smaller) is $O(\sqrt{n})$. $\endgroup$ – Erick Wong Sep 30 '14 at 15:50

Legendre's conjecture says that there is a prime between two consecutive (positive integer) squares. So between $n^2$ and $(n+2)^2$ there are two squares, so the gap between them is at most $(n+2)^2-n^2=4n+4$ (this can be improved). Let $p$ be the smaller one; then the larger one is at most $p+4n+4\le p+4\sqrt{p}+4$ and thus the gap is at most $4\sqrt{p}+4$.

The big-O notation just lets you ignore the details of what the constant is. $O(\sqrt p)$ means "bounded by a constant factor of $\sqrt p$".


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.