# Twin Prime Max Gaps (Performance Tuning)

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}.

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}]]

• 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! – Elem-Teach-w-Bach-n-Math-Ed Apr 13 '16 at 14:50
• 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. – Elem-Teach-w-Bach-n-Math-Ed Apr 13 '16 at 14:52
• My code's the one with the bug. Not sure where exactly, but it should be 12 as yours outputs. – Elem-Teach-w-Bach-n-Math-Ed Apr 13 '16 at 15:02
• @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. – wxffles Apr 13 '16 at 20:20
• Ah, that got it! Didn't even think of that! Thanks! – Elem-Teach-w-Bach-n-Math-Ed Apr 13 '16 at 21:01