Legendre's conjecture

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

Plot of the number of primes between n² and (n+1)² (sequence A014085 in OEIS)

The prime number theorem suggests the actual number of primes between n² and (n + 1)² (sequence A014085 in OEIS) 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)$. In fact the conjecture follows from Andrica's conjecture and from Oppermann's conjecture. 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 revolution of the Ulam spiral.

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 10¹⁸. A counterexample near 10¹⁸ would require a prime gap fifty million times the size of the average gap.

See also

• Bertrand's postulate
• Brocard's conjecture
• Firoozbakht’s conjecture

External links

• Weisstein, Eric W., "Legendre's conjecture", MathWorld.