An algorithm and computation to verify Legendre’s conjecture up to $$7\cdot 10^{13}$$

Abstract We state a general purpose algorithm for quickly finding primes in evenly divided sub-intervals. Legendre’s conjecture claims that for every positive integer n , there exists a prime between $$n^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:math> and $$(n+1)^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:math> . Oppermann’s conjecture subsumes Legendre’s conjecture by claiming there are primes between $$n^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:math> and $$n(n+1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and also between $$n(n+1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and $$(n+1)^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:math> . Using Cramér’s conjecture as the basis for a heuristic run-time analysis, we show that our algorithm can verify Oppermann’s conjecture, and hence also Legendre’s conjecture, for all $$n\le N$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> in time $$O( N \log N \log \log N)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>N</mml:mi> <mml:mo>log</mml:mo> <mml:mi>N</mml:mi> <mml:mo>log</mml:mo> <mml:mo>log</mml:mo> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and space $$N^{O(1/\log \log N)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mo>log</mml:mo> <mml:mo>log</mml:mo> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:math> . We implemented a parallel version of our algorithm and improved the empirical verification of Oppermann’s conjecture from the previous $$N = 2\cdot 10^{9}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> <mml:mo>·</mml:mo> <mml:msup> <mml:mn>10</mml:mn> <mml:mn>9</mml:mn> </mml:msup> </mml:mrow> </mml:math> up to $$N = 7.05\cdot 10^{13} &gt; 2^{46}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>=</mml:mo> <mml:mn>7.05</mml:mn> <mml:mo>·</mml:mo> <mml:msup> <mml:mn>10</mml:mn> <mml:mn>13</mml:mn> </mml:msup> <mml:mo>&gt;</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>46</mml:mn> </mml:msup> </mml:mrow> </mml:math> , so we were finding 27 digit primes. The computation ran for about half a year on each of two platforms: four Intel Xeon Phi 7210 processors using a total of 256 cores, and a 192-core cluster of Intel Xeon E5-2630 2.3GHz processors.