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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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}]]
Improve this answer
$\endgroup$
5
  • $\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$ Commented Apr 13, 2016 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$ Commented Apr 13, 2016 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$ Commented Apr 13, 2016 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$ Commented Apr 13, 2016 at 20:20
  • $\begingroup$ Ah, that got it! Didn't even think of that! Thanks! $\endgroup$ Commented Apr 13, 2016 at 21:01

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.