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

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\) $n^2$ and \((n+1)^2\) ${(n+1)}^2$ . Oppermann’s conjecture subsumes Legendre’s conjecture by claiming there are primes between \(n^2\) $n^2$ and \(n(n+1)\) $n(n+1)$ and also between \(n(n+1)\) $n(n+1)$ and \((n+1)^2\) ${(n+1)}^2$ . 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\) $n\le N$ in time \(O( N \log N \log \log N)\) $O(NlogNloglogN)$ and space \(N^{O(1/\log \log N)}\) $N^{O(1/loglogN)}$ . 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}\) $N=2·{10}^9$ up to \(N = 7.05\cdot 10^{13} > 2^{46}\) $N=7.05·{10}^{13}>2^{46}$ , 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.