9
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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[[1]] > b[[1]], 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}} *)
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – martin Aug 25 '15 at 23:05
  • $\begingroup$ No ideas yet, looking through my books... Have you seen papers by Bertil Nyman and Thomas Nicely? and references therein? $\endgroup$ – KennyColnago Aug 25 '15 at 23:30
  • $\begingroup$ 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? $\endgroup$ – martin Aug 25 '15 at 23:46
  • $\begingroup$ am away for a couple of days, so will test when I get back & most likely accept then :) $\endgroup$ – martin Aug 29 '15 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.