Primes Between Consecutive Squares:
How many primes are there between n2 and (n+1)2?

Legendre's conjecture states that, for each positive integer n, there is at least one prime between n2 and (n+1)2. Even a cursory check shows that there are in fact more than one. Just how many more? Let us perform a hands-on investigation.

Here are two hypotheses (both are apparently true):
(A) Legendre's conjecture.  For each integer n > 0, there is at least one prime between n2 and (n+1)2.
(B) For each integer n > 0, there are at least [] primes between n2 and (n+1)2.
The expression [x] denotes the integer part of x.

Consider statement (B). Note that it is stronger than Legendre's conjecture (A) – that is, (A) follows from (B). On this page, we are going to perform a computational check of statement (B); thus we will also check Legendre's conjecture (A) at the same time. Note, however, that a direct computational check is not a proof. We can only check a finite number of values, whereas the above statements involve an infinite number of values of n. It seems extremely unlikely – but still remotely possible – that an abnormally big prime gap might invalidate the above statements. For now, we do know that prime gaps that large are never observed up to 18-digit primes. (We can say this with certainty because the largest gap between any primes up to 18 digits is only 1442; this gap happens between the primes 804212830686677669 and 804212830686679111. The interval (n2, (n+1)2) is wider than 1442 when n > 720, so Legendre's conjecture seems a safe bet, up to 18-digit primes.)

Back to statement (B). This statement is suggested, in part, by the following observations:
(1) For integer m > 6776941, each interval (m4/3, (m+1)4/3) contains a prime (generalized Legendre conjecture, case 4/3).
(2) For positive integers m and n, one can show that a single interval (n2, (n+1)2) contains at least [] intervals (m4/3, (m+1)4/3).
(3) Combining (1) and (2), we can expect statement (B) to be valid for n large enough – namely, for integer n > 35811 = [67769412/3].

However, the n > 0 part of statement (B) does not seem to follow from anything (other than a direct computational check). So it is quite surprising that (B) apparently does hold for all positive n. The table below presents a direct computational check of statement (B). You can save this page locally, together with primefactors.js, and re-run the check for any values of n; just modify the assigned start and stop values for continuous range verification; for example, showVerification(start=200,stop=300). You are welcome to perform focused checks for known large prime gaps (lists of prime gaps are available online). Alternatively, you can test any prediction as to the number of primes in the interval (n2, (n+1)2); to do so, simply change the value assigned to the minPrimes variable. (Search the code for  minPrimes = and, for the right-hand side, substitute whatever expression you would like to test. For example, by setting the expected minimum number of primes to one, minPrimes = 1, we would check the classical Legendre's conjecture.)

Now that we know there are at least that many primes in the interval (n2, (n+1)2), we can appreciate just how frustrating it is for mathematicians to lack a rigorous proof that there is at least one prime in this interval – in spite of trying for 200 years to find such a proof! Could it be that Legendre's conjecture is one of those elusive statements that are true but cannot be proved?

                                                       How many primes?
      n      n2    <    primes    <  (n+1)2      √n    expected  actual   OK/fail  

Post Scriptum: Here are some additional hypotheses – all of them appear to be true, too:
(C) For each integer n > 23, there are at least [1.5] primes between n2 and (n+1)2.
(D) For each integer n > 137, there are at least [2] primes between n2 and (n+1)2.
(E) For each integer n > 425, there are at least [3] primes between n2 and (n+1)2.
Here, again, [x] denotes the integer part of x. We leave checking statements (C), (D), and (E) to the interested reader.

Copyright © 2011,