2
$\begingroup$

Ok, let's build a foundation here:

A common way of testing primality, is dividing by all primes smaller than the number's square root. For instance, $97$ is prime because dividing by none of the following: {$2,3,5,7$} gives a remainder of $0$. In fact, we can test for primality using the same set of four numbers as long as the number we're testing is between $49$ and $121$.

So let's use that knowledge to look for the largest possible gap in primes between $49$ and $121$. When $49$ is divided by the numbers: {$2,3,5,7$}, you get remainders of {$1,1,4,0$}. $50$ would be {$0,2,0,1$}, adding one to each. When we get to $259$, we're back to {$1,1,4,0$}. Question is, what is the largest gap between numbers where that set doesn't contain a $0$? Using Mathematica we can brute force test with the following code:

consecutiveValues[l_List] := Length /@ Split[l];
plist=Table[Prime[n],{n,1,4}];
mp=Apply[Times,plist];
mdna=Outer[Mod,{m },plist];
tptest=Table[MemberQ[{mdna},0,Infinity],{m,49,mp+49}];
AbsoluteTiming[(Max[consecutiveValues[tptest]]+1)]

Which gives:

{0.000076,10}

So $10$ composites between each prime. Easy enough. Problem is, this gets exponentially more memory intensive as $n$ increases.


Well, now that you get the idea in relation to primes, here's what I'm doing for twin primes:

consecutiveValues[l_List] := Length /@ Split[l]; (*# of consecutive false*)
plist=Table[Prime[n],{n,3,8}];
mp=Apply[Times,plist];
mdna=Outer[Mod,{6m-3 },plist];
tptest=Table[{MemberQ[{mdna},2,Infinity]||MemberQ[{mdna},4,Infinity]},{m,5,5+Ceiling[mp/6]}];
AbsoluteTiming[(Max[consecutiveValues[tptest]]+1)*6]

Using this yields:

{0.086062,150}

This means that in the range {$19^2$ to $23^2$}, a range of 168, there can only be a max gap between twin primes of 150. We can thus guarantee that there is at least 1 twin prime pair in this range.

This code takes advantage of the fact that a number is 4 and 2 more than the two primes of a twin prime pair if its list of remainders contains no 2's or 4's. Otherwise, a number 2 or 4 below it is composite. I've tweaked the code slightly for speed and efficiency (using my very basic knowledge), and have already asked this on Math SE searching for something mathematically I could do differently.


My question is:

What can I do as far as code tweaks that would find twin prime gaps within reasonable memory limits? Right now, Wolfram Programming Lab exits when I use anything above {n,1,9}.

$\endgroup$
4
$\begingroup$

To fix the memory problems you could rewrite it in a procedural style. It's probably more than a tweak, a bit ugly, and a bit slower. But you can go forever without having to worry about memory.

ClearAll@fail;
fail = Compile[{{m, _Integer}, {p, _Integer, 1}},
   MemberQ[Mod[6 m - 3, #] & /@ p, 2] || MemberQ[Mod[6 m - 3, #] & /@ p, 4]];

ClearAll@twingaps; 
twingaps[plist_] := 
 Module[{m, mp, mm, failCount = 0, maxFailCount = 0},
  mp = Apply[Times, plist];
  mm = 5 + Ceiling[mp/6];
  For[m = 5, m <= mm, ++m,
    If[fail[m, plist], ++failCount,
      maxFailCount = Max[maxFailCount, failCount]; failCount = 0];
    ]~Monitor~(100. m/mm);
  maxFailCount = Max[maxFailCount, failCount];
  6 (maxFailCount + 1)
  ]

twingaps[Table[Prime[n], {n, 1, 8}]]
$\endgroup$
  • $\begingroup$ Awesome! This did solve the memory issue! You're right tho, that the time becomes a problem, I now found that for $n=9$ I get a gap of 204... problem is $n=10$ errors out because of time limitations now. The rate of increase of time says even with some massive tweaking, I doubt I'll ever be able to get $n=12$ with the math the code's running. Gonna have to see what I can do mathematically instead I guess. Will give some time for other answers, but I doubt anyone's going to be able to give anything significantly better. Thanks! $\endgroup$ – Elem-Teach-w-Bach-n-Math-Ed Apr 13 '16 at 14:50
  • $\begingroup$ Oh, I did notice something. $n=3$ gives a different gap for our two codes. One gives 12, the other 18. Not exactly sure why... Every other input matches up. $\endgroup$ – Elem-Teach-w-Bach-n-Math-Ed Apr 13 '16 at 14:52
  • $\begingroup$ My code's the one with the bug. Not sure where exactly, but it should be 12 as yours outputs. $\endgroup$ – Elem-Teach-w-Bach-n-Math-Ed Apr 13 '16 at 15:02
  • 1
    $\begingroup$ @Elem-Teach-w-Bach-n-Math-Ed Your max of consecutiveValues bit doesn't take into account if it's true or false. For small ranges of primes sometimes the longest run is the wrong type. $\endgroup$ – wxffles Apr 13 '16 at 20:20
  • $\begingroup$ Ah, that got it! Didn't even think of that! Thanks! $\endgroup$ – Elem-Teach-w-Bach-n-Math-Ed Apr 13 '16 at 21:01

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.