# Finding large prime gaps

I am using basic searches for prime gaps as follows:

greater[list_] := First@# & /@ Split[list, Greater]
primeG[nn_] := With[{aa = Prime@Range@PrimePi@(nn)},
With[{bb = (Rest@aa - Most@aa)},
With[{cc = (First@# & /@ Split@Nest[greater, bb, Round@(Log@nn^2)])},
With[{dd = Prime@First@Flatten@# & /@ (Position[bb, #] & /@ cc)},
Transpose@{cc - 1, dd}]]]]

primeGmax[r1_, r2_] :=
With[{bb = Split@PrimeQ@Range[If[EvenQ@r1 == True, r1 + 1, r1], r2, 2]},
With[{aa = Length@# & /@ bb}, With[{dd = Max@aa},
With[{cc = Position[aa, dd][[1, 1]]},
2 {dd + 1/2, Length@Flatten@Take[bb, cc] - dd + If[EvenQ@r1 == True, r1 + 1, r1]/2 - 1}]]]]

primeG[10^3]
primeGmax[10^2, 10^3]

(*
{{0, 2}, {1, 3}, {3, 7}, {5, 23}, {7, 89}, {13, 113}, {17, 523}, {19, 887}}
{19, 887}
*)


This also appears to work for larger numbers:

With[{pp = 1425172824437000000}, primeGmax[pp, pp + 10^6]]
(*{1475, 1425172824437699411}*)


The Mathematica code on these OEIS sequences (A008996, A002386) seems to be no more efficient.

Is there a cleverer way, using Mod small primes other than 2? I know there are programs written especially for this purpose - is it better to use those for large nujmbers, or is Mathematica a viable platform for these kind of searches?

I rewrote your primeG, ignorant of clever methods. Nevertheless, with [[All,1]] and the fourth argument to Position you can get a 50% speed increase. Also, since you already calculate the primes in aa, there is no need to use Prime in calculating dd.

MartinPrimeGaps[nn_]:=
With[{aa = Prime@Range@PrimePi@nn},
With[{bb = Differences[aa]},
With[{cc = Split[Nest[Split[#, Greater][[All, 1]] &, bb,
Round@(Log@nn^2)]][[All, 1]]},
Transpose[{cc - 1,
aa[[Flatten[Position[bb, #, 1, 1] & /@ cc]]]}]]]]


Update I rewrote primeGmax in two different ways. The first MaxPrimeGap1 uses a lot of memory when a large range is required, and is cleaner but not significantly faster than primeGmax.

MaxPrimeGap1[r1_?OddQ, r2_] :=
Block[{p = Range[r1, r2, 2], gaps, maxgap},
gaps = Differences[p = Pick[p, PrimeQ[p]]] - 1;
maxgap = Max[gaps];
{maxgap, p[[Position[gaps, maxgap, 1, 1][[1, 1]]]]}]


The second MaxPrimeGap2 uses almost no memory, but NextPrime makes it significantly slower than MaxPrimeGap1.

MaxPrimeGap2[r1_?OddQ, r2_] :=
Block[{p1 = r1, p2 = NextPrime[r1], g, b = {0, 0}},
g = {p2 - p1 - 1, p1};
While[p1 < r2,
p2 = NextPrime[p1];
g = {p2 - p1 - 1, p1};
p1 = p2;
If[g[] > b[], b = g]
];
b]


The slow part of the code is testing for primality. Specifying only odd numbers in the Range statement cuts the number of tests in half. Sieve methods, which continue cutting numbers in the range, are very fast. I rewrote code from @SimonWoods here to return a list of candidate numbers between nmin and nmax not divisible by the first m primes.

CandidatePrimes[nmin_Integer, nmax_Integer, m_Integer] :=
Module[{y = Range[nmin, nmax], min, max = nmax - nmin + 1},
Map[If[(min = # - Mod[nmin, #] + 1) <= max, (y[[min ;; max ;; #]] = 0)] &,
Prime[Range[m]]];
SparseArray[y]["NonzeroValues"]]


Now use CandidatePrimes to reduce the number of prime checks.

MaxPrimeGap3[r1_?OddQ, r2_Integer, m_Integer] :=
Block[{p = CandidatePrimes[r1, r2, m], gaps, maxgap},
gaps = Differences[p = Pick[p, PrimeQ[p]]] - 1;
maxgap = Max[gaps];
{maxgap, p[[Position[gaps, maxgap, 1, 1][[1, 1]]]]}]


If you have parallel processors, then it is faster to use Pick[p,ParallelMap[PrimeQ,p]] instead of Pick[p,PrimeQ[p]. Call this version MaxPrimeGap4.

Set the lower limit to a large prime, NextPrime[10^12].

AbsoluteTiming[MaxPrimeGap1[1000000000039, 1000000000039 + 10^7]]
(* {16.682, {321, 1000008002317}} *)

AbsoluteTiming[MaxPrimeGap3[1000000000039, 1000000000039 + 10^7, 300]]
(* {13.427, {321, 1000008002317}} *)


Using 8 parallel kernels, MaxPrimeGap4 takes 3.9 s. Another example:

AbsoluteTiming[MaxPrimeGap4[1000000000000037, 1000000000000037 + 10^8, 1000]]
(* {36.631, {489, 1000000025764111}} *)

• great - thanks :) I am really most interested in extending the range for primeGmax ($10^7$ is a drop in the ocean at that height) - any ideas? Aug 25, 2015 at 23:05
• No ideas yet, looking through my books... Have you seen papers by Bertil Nyman and Thomas Nicely? and references therein? Aug 25, 2015 at 23:30
• have been browsing Thomas Nicely's website, but unfortunately I am rather ignorant about math progs other than MMA - do you think the PARI, etc,. progs could be adapted to MMA effectively / efficiently? Aug 25, 2015 at 23:46
• am away for a couple of days, so will test when I get back & most likely accept then :) Aug 29, 2015 at 23:05