Triangle primes

[Max]

On 4/15/06, Jim Nastos <nastos at cs.ualberta.ca> wrote:

>         A111252  Primes p such that the difference between the closest squares
>         surrounding p is prime
>
>    which is essentially saying that if (n+1)^2 - n^2 is prime, then all
> primes between n^2 and (n+1)^2 are in A111252.
>    Now, since (n+1)^2 - n^2 is just 2n+1, then clearly every odd prime
> corresponds to one of these intervals (bounded by consecutive squares) so
> clearly, this sequence is infinite...

Yes, there is an infinite sequence of such intervals. BUT it is not
known in advance if they contain any primes. This is a famous
Legendre's conjecture (also known as one of <a
href="http://mathworld.wolfram.com/LandausProblems.html">Landau's
Problems</a>) saying that there always exists a prime between n^2 and
(n+1)^2. And it is still an open problem.

Therefore, the infiniteness of A111252 is equivalent to (yet unproved)
Legendre's conjecture.

Max