Finding Prime Quadruplets with JavaScript

Table of ContentsDoing Math with JavaScript

Prime quadruplets are dense clusters of four primes that have the form {p, p+2, p+6, p+8}. Except for the first quadruplet {5, 7, 11, 13}, all primes in a quadruplets start with the same decimal digit(s) and differ only in the last digit. Examples of prime quadruplets are {11, 13, 17, 19}, {101, 103, 107, 109}, {821, 823, 827, 829}, or {1871, 1873, 1877, 1879}. One can prove that all prime quadruplets – except the smallest one {5, 7, 11, 13} – have the form {30i + 11, 30i + 13, 30i + 17, 30i + 19} for a certain integer i. Our definition implies that the width of a prime quadruplet is 8; it also implies that three consecutive odd numbers {3, 5, 7} cannot be part of a quadruplet. (Thus, the sets of primes {2,3,5,7} and {3,5,7,11} are not prime quadruplets by our definition. These sets do not have the form {p, p+2, p+6, p+8} described above.) Prime quadruplets are rare – so rare that mathematicians do not even know if there is an infinite number of prime quadruplets or only finitely many. However, if you have a JavaScript-enabled Web browser, you can find your very own prime quadruplet in a matter of seconds. (For 15- or 16-digit prime quadruplets, though, you may need to wait longer – they tend to be very far apart.)

Here is a JavaScript function nextPrimeQuad(n) for finding the next prime quadruplet greater than n. This function relies on isPrime() to test whether a number is prime; so isPrime() should be fast in order for nextPrimeQuad(n) to return a result in a reasonable time.

// function nextPrimeQuad(n) returns:
// * the smallest prime in the next prime quadruplet greater than n
// * NaN if such a prime is not a representable integer

function nextPrimeQuad(n) {
 if (isNaN(n) || !isFinite(n)) return NaN; 
 if (n<5) return 5;
 if (n<11) return 11;
 for (var i=30*Math.ceil(Math.floor(n-10)/30); i<9007199254740880; i+=30) {
  if (pscreen(i+11) && pscreen(i+13) && pscreen(i+17) && pscreen(i+19)
   && isPrime(i+11) && isPrime(i+13) && isPrime(i+17) && isPrime(i+19))
    return i+11;
 }
 return NaN;
}

function pscreen(n) {
 // screen out most non-primes early on
 if (n<=109
 || n%3 && n%5 && n%7 && n%11 && n%13 && n%17 && n%19
 && n%23 && n%29 && n%31 && n%37 && n%41 && n%43 && n%47
 && n%53 && n%59 && n%61 && n%67 && n%71 && n%73 && n%79
 && n%83 && n%89 && n%97 && n%101 && n%103 && n%107 && n%109) {
  return true;  
 }
 return false;
}

Click the Run button to find prime quadruplets by calling the nextPrimeQuad(n) in the left column:

Finding a 15- or 16-digit prime quadruplet may take from a couple of seconds to several minutes on a modern laptop or desktop. Here are a few results:

The first ten 15-digit prime quadruplets
Start by calling nextPrimeQuad(100000000000000)
Continue using nextPrimeQuad(last_result)
100000000945721 100000000945723 100000000945727 100000000945729
100000000959491 100000000959493 100000000959497 100000000959499
100000000994471 100000000994473 100000000994477 100000000994479
100000001725991 100000001725993 100000001725997 100000001725999
100000001865851 100000001865853 100000001865857 100000001865859
100000002137681 100000002137683 100000002137687 100000002137689
100000002163091 100000002163093 100000002163097 100000002163099
100000002348011 100000002348013 100000002348017 100000002348019
100000002961751 100000002961753 100000002961757 100000002961759
100000003068851 100000003068853 100000003068857 100000003068859

The first ten 16-digit prime quadruplets
Start by calling nextPrimeQuad(1000000000000000)
Continue using nextPrimeQuad(last_result)
1000000000067441 1000000000067443 1000000000067447 1000000000067449
1000000001137931 1000000001137933 1000000001137937 1000000001137939
1000000001519411 1000000001519413 1000000001519417 1000000001519419
1000000001794691 1000000001794693 1000000001794697 1000000001794699
1000000001800691 1000000001800693 1000000001800697 1000000001800699
1000000002108461 1000000002108463 1000000002108467 1000000002108469
1000000002504311 1000000002504313 1000000002504317 1000000002504319
1000000002620231 1000000002620233 1000000002620237 1000000002620239
1000000002905081 1000000002905083 1000000002905087 1000000002905089
1000000003185641 1000000003185643 1000000003185647 1000000003185649

The last eleven prime quadruplets under 253
Start by calling nextPrimeQuad(9007199250000000)
Continue using nextPrimeQuad(last_result)
9007199250286661 9007199250286663 9007199250286667 9007199250286669 
9007199251064711 9007199251064713 9007199251064717 9007199251064719 
9007199251126751 9007199251126753 9007199251126757 9007199251126759 
9007199251285511 9007199251285513 9007199251285517 9007199251285519 
9007199251368671 9007199251368673 9007199251368677 9007199251368679 
9007199251935581 9007199251935583 9007199251935587 9007199251935589 
9007199252679071 9007199252679073 9007199252679077 9007199252679079 
9007199252684201 9007199252684203 9007199252684207 9007199252684209 
9007199253663461 9007199253663463 9007199253663467 9007199253663469 
9007199253668591 9007199253668593 9007199253668597 9007199253668599 
9007199254561301 9007199254561303 9007199254561307 9007199254561309 
Reached 9007199254740991, the maximum representable odd integer     
The bottom table shows the last eleven prime quadruplets under 253. (Odd integers greater than 9007199254740992 = 253 are not representable as JavaScript numbers.) The longest function call in this series was nextPrimeQuad(9007199252684201) – it took several minutes to produce 9007199253663461. The next call nextPrimeQuad(9007199253663461) produced 9007199253668591 in just five seconds. This shows that prime quadruplets are not only very rare but also very unevenly distributed: a 16-digit quadruplet may be a hundred thousand apart from the previous one but only thousands apart from the next one.

See also:
Twin primes
Prime sextuplets
Maximal gaps between prime k-tuples

Doing Math with JavaScript. Copyright © 1999-2011, JavaScripter.net.