# Legendre's conjecture

Plot of the number of primes between n2 and (n + 1)2

Legendre's conjecture, proposed by Adrien-Marie Legendre, states that there is a prime number between n2 and (n + 1)2 for every positive integer n. The conjecture is one of Landau's problems (1912) and remains unsolved.

The prime number theorem suggests the actual number of primes between n2 and (n + 1)2 is about n/ln(n), i.e. about as many as the number of primes less than or equal to n.

If Legendre's conjecture is true, the gap between any two successive primes would be $O(\sqrt p)$. Two stronger conjectures, Andrica's conjecture and Oppermann's conjecture, also both imply that the gaps have the same magnitude. Harald Cramér conjectured that the gap is always much smaller, $O(\log^2 p)$. If Cramér's conjecture is true, Legendre's conjecture would follow for all sufficiently large numbers. Cramér also proved that the Riemann hypothesis implies a weaker bound of $O(\sqrt p\log p)$ on the size of the largest prime gaps. Legendre's conjecture implies that at least one prime can be found in every half revolution of the Ulam spiral.

Baker, Harman and Pintz proved that there is a prime in the interval $[x,\,x+O(x^{21/40})]$ for all large $x$.[1]

Because the conjecture follows from Andrica's conjecture, it suffices to check that each prime gap starting at p is smaller than $2\sqrt p.$ A table of maximal prime gaps shows that the conjecture holds to 1018. A counterexample near 1018 would require a prime gap fifty million times the size of the average gap.