Legendre's conjecture

Legendre's conjecture, proposed by Adrien-Marie Legendre, states that there is a prime number between

for every positive integer

[1] The conjecture is one of Landau's problems (1912) on prime numbers, and is one of many open problems on the spacing of prime numbers.

If Legendre's conjecture is true, the gap between any prime p and the next largest prime would be

, as expressed in big O notation.

[a] It is one of a family of results and conjectures related to prime gaps, that is, to the spacing between prime numbers.

Others include Bertrand's postulate, on the existence of a prime between

, Oppermann's conjecture on the existence of primes between

, Andrica's conjecture and Brocard's conjecture on the existence of primes between squares of consecutive primes, and Cramér's conjecture that the gaps are always much smaller, of the order

( log ⁡ p

If Cramér's conjecture is true, Legendre's conjecture would follow for all sufficiently large n. Harald Cramér also proved that the Riemann hypothesis implies a weaker bound of

log ⁡ p )

on the size of the largest prime gaps.

[2] By the prime number theorem, the expected number of primes between

, and it is additionally known that for almost all intervals of this form the actual number of primes (OEIS: A014085) is asymptotic to this expected number.

[3] Since this number is large for large

, this lends credence to Legendre's conjecture.

[4] It is known that the prime number theorem gives an accurate count of the primes within short intervals, either unconditionally[5] or based on the Riemann hypothesis,[6] but the lengths of the intervals for which this has been proven are longer than the intervals between consecutive squares, too long to prove Legendre's conjecture.

It follows from a result by Ingham that for all sufficiently large

, there is a prime between the consecutive cubes

[7][8] Dudek proved that this holds for all

[9] Dudek also proved that for

and any positive integer

Mattner lowered this to

by Cully-Hugill.

[11] Baker, Harman, and Pintz proved that there is a prime in the interval

[12] A table of maximal prime gaps shows that the conjecture holds to at least

This number theory-related article is a stub.

You can help Wikipedia by expanding it.