Prime triplets
- Task
Find and show members of prime triples (p, p+2, p+6), where p < 5500
- See also
-
- The OEIS entry: A022004 - Initial members of prime triples (p, p+2, p+6)
- The Wikipedia entry: Prime triplet
- The MathWorld entry: Prime Triplet
- The RosettaCode task for just (p,p+4): Cousin primes
- The RosettaCode task for other patterns of primes: Successive prime differences
ALGOL 68
Using code from Successive_prime_differences#ALGOL_68 <lang algol68>BEGIN # find primes p where p+2 and p+6 are also prime #
# reurns a list of primes up to n # PROC prime list = ( INT n )[]INT: BEGIN # sieve the primes to n # INT no = 0, yes = 1; [ 1 : n ]INT p; p[ 1 ] := no; p[ 2 ] := yes; FOR i FROM 3 BY 2 TO n DO p[ i ] := yes OD; FOR i FROM 4 BY 2 TO n DO p[ i ] := no OD; FOR i FROM 3 BY 2 TO ENTIER sqrt( n ) DO IF p[ i ] = yes THEN FOR s FROM i * i BY i + i TO n DO p[ s ] := no OD FI OD; # replace the sieve with a list # INT p pos := 0; FOR i TO n DO IF p[ i ] = yes THEN p[ p pos +:= 1 ] := i FI OD; p[ 1 : p pos ] END # prime list # ; # prints the elements of list # PROC print list = ( INT width, []INT list )VOID: BEGIN print( ( "[" ) ); FOR i FROM LWB list TO UPB list DO print( ( " ", whole( list[ i ], width ) ) ) OD; print( ( " ]" ) ) END # print list # ; # attempts to find patterns in the differences of primes and prints the results # PROC try differences = ( []INT primes, []INT pattern )VOID: BEGIN INT pattern length = ( UPB pattern - LWB pattern ) + 1; [ 1 : pattern length + 1 ]INT first; FOR i TO UPB first DO first[ i ] := 0 OD; [ 1 : pattern length + 1 ]INT last; FOR i TO UPB last DO last[ i ] := 0 OD; INT count := 0; FOR p FROM LWB primes + pattern length TO UPB primes DO BOOL matched := TRUE; INT e pos := LWB pattern; FOR e FROM p - pattern length TO p - 1 WHILE matched := primes[ e + 1 ] - primes[ e ] = pattern[ e pos ] DO e pos +:= 1 OD; IF matched THEN # found a matching sequence # count +:= 1; print list( -4, primes[ p - pattern length : p ] ); IF count MOD 6 = 0 THEN print( ( newline ) ) ELSE print( ( " " ) ) FI FI OD; print( ( newline, "Found ", whole( count, 0 ), " prime sequence(s) that differ by: " ) ); print list( 0, pattern ); print( ( newline ) ) END # try differences # ; INT max number = 5 500; []INT p list = prime list( max number - 1 ); print( ( "Prime triplets under ", whole( max number, 0 ), ":", newline ) ); try differences( p list, ( 2, 4 ) )
END</lang>
- Output:
Prime triplets under 5500: [ 5 7 11 ] [ 11 13 17 ] [ 17 19 23 ] [ 41 43 47 ] [ 101 103 107 ] [ 107 109 113 ] [ 191 193 197 ] [ 227 229 233 ] [ 311 313 317 ] [ 347 349 353 ] [ 461 463 467 ] [ 641 643 647 ] [ 821 823 827 ] [ 857 859 863 ] [ 881 883 887 ] [ 1091 1093 1097 ] [ 1277 1279 1283 ] [ 1301 1303 1307 ] [ 1427 1429 1433 ] [ 1481 1483 1487 ] [ 1487 1489 1493 ] [ 1607 1609 1613 ] [ 1871 1873 1877 ] [ 1997 1999 2003 ] [ 2081 2083 2087 ] [ 2237 2239 2243 ] [ 2267 2269 2273 ] [ 2657 2659 2663 ] [ 2687 2689 2693 ] [ 3251 3253 3257 ] [ 3461 3463 3467 ] [ 3527 3529 3533 ] [ 3671 3673 3677 ] [ 3917 3919 3923 ] [ 4001 4003 4007 ] [ 4127 4129 4133 ] [ 4517 4519 4523 ] [ 4637 4639 4643 ] [ 4787 4789 4793 ] [ 4931 4933 4937 ] [ 4967 4969 4973 ] [ 5231 5233 5237 ] [ 5477 5479 5483 ] Found 43 prime sequence(s) that differ by: [ 2 4 ]
AWK
<lang AWK>
- syntax: GAWK -f PRIME_TRIPLETS.AWK
BEGIN {
start = 1 stop = 5499 for (i=start; i<=stop; i++) { if (is_prime(i+6) && is_prime(i+2) && is_prime(i)) { printf("%d %d %d\n",i,i+2,i+6) count++ } } printf("Prime Triplets %d-%d: %d\n",start,stop,count) exit(0)
} function is_prime(x, i) {
if (x <= 1) { return(0) } for (i=2; i<=int(sqrt(x)); i++) { if (x % i == 0) { return(0) } } return(1)
} </lang>
- Output:
5 7 11 11 13 17 17 19 23 41 43 47 101 103 107 107 109 113 191 193 197 227 229 233 311 313 317 347 349 353 461 463 467 641 643 647 821 823 827 857 859 863 881 883 887 1091 1093 1097 1277 1279 1283 1301 1303 1307 1427 1429 1433 1481 1483 1487 1487 1489 1493 1607 1609 1613 1871 1873 1877 1997 1999 2003 2081 2083 2087 2237 2239 2243 2267 2269 2273 2657 2659 2663 2687 2689 2693 3251 3253 3257 3461 3463 3467 3527 3529 3533 3671 3673 3677 3917 3919 3923 4001 4003 4007 4127 4129 4133 4517 4519 4523 4637 4639 4643 4787 4789 4793 4931 4933 4937 4967 4969 4973 5231 5233 5237 5477 5479 5483 Prime Triplets 1-5499: 43
Factor
<lang factor>USING: arrays kernel lists lists.lazy math math.primes math.primes.lists prettyprint sequences ;
lprimes ! An infinite lazy list of primes [ dup 2 + dup 4 + 3array ] lmap-lazy ! Map primes to their triplets (e.g. 2 -> { 2 4 8 }) [ [ prime? ] all? ] lfilter ! Select triplets which contain only primes [ first 5500 < ] lwhile ! Make the list end eventually... [ . ] leach ! Print each item in the list</lang>
- Output:
{ 5 7 11 } { 11 13 17 } { 17 19 23 } { 41 43 47 } { 101 103 107 } { 107 109 113 } { 191 193 197 } { 227 229 233 } { 311 313 317 } { 347 349 353 } { 461 463 467 } { 641 643 647 } { 821 823 827 } { 857 859 863 } { 881 883 887 } { 1091 1093 1097 } { 1277 1279 1283 } { 1301 1303 1307 } { 1427 1429 1433 } { 1481 1483 1487 } { 1487 1489 1493 } { 1607 1609 1613 } { 1871 1873 1877 } { 1997 1999 2003 } { 2081 2083 2087 } { 2237 2239 2243 } { 2267 2269 2273 } { 2657 2659 2663 } { 2687 2689 2693 } { 3251 3253 3257 } { 3461 3463 3467 } { 3527 3529 3533 } { 3671 3673 3677 } { 3917 3919 3923 } { 4001 4003 4007 } { 4127 4129 4133 } { 4517 4519 4523 } { 4637 4639 4643 } { 4787 4789 4793 } { 4931 4933 4937 } { 4967 4969 4973 } { 5231 5233 5237 } { 5477 5479 5483 }
Fermat
<lang fermat>for i=3,5499,2 do if Isprime(i)=1 and Isprime(i+2)=1 and Isprime(i+6)=1 then !!(i,i+2,i+6) fi od</lang>
FreeBASIC
<lang freebasic>#include "isprime.bas" for p as uinteger = 3 to 5499 step 2
if not isprime(p+6) then continue for if not isprime(p+2) then continue for if not isprime(p) then continue for print using "[#### #### ####] ";p;p+2;p+6;
next p</lang>
- Output:
[ 5 7 11] [ 11 13 17] [ 17 19 23] [ 41 43 47] [ 101 103 107] [ 107 109 113] [ 191 193 197] [ 227 229 233] [ 311 313 317] [ 347 349 353] [ 461 463 467] [ 641 643 647] [ 821 823 827] [ 857 859 863] [ 881 883 887] [1091 1093 1097] [1277 1279 1283] [1301 1303 1307] [1427 1429 1433] [1481 1483 1487] [1487 1489 1493] [1607 1609 1613] [1871 1873 1877] [1997 1999 2003] [2081 2083 2087] [2237 2239 2243] [2267 2269 2273] [2657 2659 2663] [2687 2689 2693] [3251 3253 3257] [3461 3463 3467] [3527 3529 3533] [3671 3673 3677] [3917 3919 3923] [4001 4003 4007] [4127 4129 4133] [4517 4519 4523] [4637 4639 4643] [4787 4789 4793] [4931 4933 4937] [4967 4969 4973] [5231 5233 5237] [5477 5479 5483]
Go
<lang go>package main
import (
"fmt" "rcu"
)
func main() {
c := rcu.PrimeSieve(5505, false) var triples [][3]int fmt.Println("Prime triplets: p, p + 2, p + 6 where p < 5,500:") for i := 3; i < 5500; i += 2 { if !c[i] && !c[i+2] && !c[i+6] { triples = append(triples, [3]int{i, i + 2, i + 6}) } } for _, triple := range triples { var t [3]string for i := 0; i < 3; i++ { t[i] = rcu.Commatize(triple[i]) } fmt.Printf("%5s %5s %5s\n", t[0], t[1], t[2]) } fmt.Println("\nFound", len(triples), "such prime triplets.")
}</lang>
- Output:
Same as Wren entry.
GW-BASIC
<lang gwbasic>10 FOR A = 3 TO 5499 STEP 2 20 P = A 30 GOSUB 1000 40 IF Z = 0 THEN GOTO 500 50 P = A + 2 60 GOSUB 1000 70 IF Z = 0 THEN GOTO 500 80 P = A + 6 90 GOSUB 1000 100 IF Z = 1 THEN PRINT A,A+2,A+6 500 NEXT A 510 END 1000 Z = 1 : I = 2 1010 IF P MOD I = 0 THEN Z = 0 : RETURN 1020 I = I + 1 1030 IF I*I > P THEN RETURN 1040 GOTO 1010</lang>
Julia
<lang julia>using Primes
pmask = primesmask(1, 5505) foreach(n -> println([n, n + 2, n + 6]), filter(n -> pmask[n] && pmask[n + 2] && pmask[n + 6], 1:5500))
</lang>
- Output:
[5, 7, 11] [11, 13, 17] [17, 19, 23] [41, 43, 47] [101, 103, 107] [107, 109, 113] [191, 193, 197] [227, 229, 233] [311, 313, 317] [347, 349, 353] [461, 463, 467] [641, 643, 647] [821, 823, 827] [857, 859, 863] [881, 883, 887] [1091, 1093, 1097] [1277, 1279, 1283] [1301, 1303, 1307] [1427, 1429, 1433] [1481, 1483, 1487] [1487, 1489, 1493] [1607, 1609, 1613] [1871, 1873, 1877] [1997, 1999, 2003] [2081, 2083, 2087] [2237, 2239, 2243] [2267, 2269, 2273] [2657, 2659, 2663] [2687, 2689, 2693] [3251, 3253, 3257] [3461, 3463, 3467] [3527, 3529, 3533] [3671, 3673, 3677] [3917, 3919, 3923] [4001, 4003, 4007] [4127, 4129, 4133] [4517, 4519, 4523] [4637, 4639, 4643] [4787, 4789, 4793] [4931, 4933, 4937] [4967, 4969, 4973] [5231, 5233, 5237] [5477, 5479, 5483]
PARI/GP
<lang parigp>for(i=1,5499,if(isprime(i)&&isprime(i+2)&&isprime(i+6),print(i," ",i+2," ",i+6)))</lang>
Phix
function pt(integer p) return is_prime(p+2) and is_prime(p+6) end function sequence res = filter(get_primes_le(5500),pt) res = apply(true,sq_add,{res,{{0,2,6}}}) res = apply(true,sprintf,{{"(%d %d %d)"},res}) printf(1,"Found %d prime triplets: %s\n",{length(res),join(shorten(res,"",2),", ")})
- Output:
Found 43 prime triplets: (5 7 11), (11 13 17), ..., (5231 5233 5237), (5477 5479 5483)
Raku
Adapted from Cousin primes
Filter
Favoring brevity over efficiency due to the small range of n, the most concise solution is: <lang perl6>say grep *.all.is-prime, map { $_, $_+2, $_+6 }, 2..5500;</lang>
- Output:
((5 7 11) (11 13 17) (17 19 23) (41 43 47) (101 103 107) (107 109 113) (191 193 197) (227 229 233) (311 313 317) (347 349 353) (461 463 467) (641 643 647) (821 823 827) (857 859 863) (881 883 887) (1091 1093 1097) (1277 1279 1283) (1301 1303 1307) (1427 1429 1433) (1481 1483 1487) (1487 1489 1493) (1607 1609 1613) (1871 1873 1877) (1997 1999 2003) (2081 2083 2087) (2237 2239 2243) (2267 2269 2273) (2657 2659 2663) (2687 2689 2693) (3251 3253 3257) (3461 3463 3467) (3527 3529 3533) (3671 3673 3677) (3917 3919 3923) (4001 4003 4007) (4127 4129 4133) (4517 4519 4523) (4637 4639 4643) (4787 4789 4793) (4931 4933 4937) (4967 4969 4973) (5231 5233 5237) (5477 5479 5483))
Infinite List
A more efficient and versatile approach is to generate an infinite list of triple primes, using this info from https://oeis.org/A022004 :
- All terms are congruent to 5 (mod 6).
<lang perl6>constant @triples = (5, *+6 … *).map: -> \n { $_ if .all.is-prime given (n, n+2, n+6) }
my $count = @triples.first: :k, *.[0] >= 5500;
say .fmt('%4d') for @triples.head($count);</lang>
- Output:
5 7 11 11 13 17 17 19 23 41 43 47 101 103 107 107 109 113 191 193 197 227 229 233 311 313 317 347 349 353 461 463 467 641 643 647 821 823 827 857 859 863 881 883 887 1091 1093 1097 1277 1279 1283 1301 1303 1307 1427 1429 1433 1481 1483 1487 1487 1489 1493 1607 1609 1613 1871 1873 1877 1997 1999 2003 2081 2083 2087 2237 2239 2243 2267 2269 2273 2657 2659 2663 2687 2689 2693 3251 3253 3257 3461 3463 3467 3527 3529 3533 3671 3673 3677 3917 3919 3923 4001 4003 4007 4127 4129 4133 4517 4519 4523 4637 4639 4643 4787 4789 4793 4931 4933 4937 4967 4969 4973 5231 5233 5237 5477 5479 5483
REXX
<lang rexx>/*REXX program finds prime triplets: P, P+2, P+6 are primes, and P < some specified N*/ parse arg hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 5500 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 4 /* " " " " " " */ call genP hi + 6 /*build semaphore array for low primes.*/
do p=1 while @.p<hi end /*p*/; lim= p-1 /*set LIM to the Pth prime. */
w= 30 /*width of a prime triplet in a column.*/ __= ' '; @trip= ' prime triplets: p, p+2, p+6 are primes, and p < ' commas(hi) if cols>0 then say ' index │'center(@trip, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') Tprimes= 0; idx= 1 /*initialize # prime triplets & index.*/ $= /*a list of prime triplets (so far). */
do j=1 to lim /*look for prime triplets within range.*/ p2= @.j + 2; if \!.p2 then iterate /*is P2 prime? No, then skip it. */ p6= p2 + 4; if \!.p6 then iterate /* " P6 " " " " " */ Tprimes= Tprimes + 1 /*bump the number of prime triplets. */ if cols==0 then iterate /*Build the list (to be shown later)? */ @@@= commas(@.j)__ commas(p2)__ commas(p6) /*add commas & blanks to prime triplet.*/ $= $ left( '('@@@")", w) /*add a prime triplet ──► the $ list.*/ if Tprimes//cols\==0 then iterate /*have we populated a line of output? */ say center(idx, 7)'│' strip(substr($, 2), 'T'); $= /*show what we have so far.*/ idx= idx + cols /*bump the index count for the output*/ end /*j*/
if $\== then say center(idx, 7)"│" strip(substr($, 2), 'T') /*possible show residual*/ if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─') say say 'Found ' commas(Tprimes) @trip exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: !.= 0; parse arg limit /*placeholders for primes (semaphores).*/
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */ !.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " flags. */ #=5; s.#= @.# **2 /*number of primes so far; prime². */ /* [↓] generate more primes ≤ high.*/ do j=@.#+2 by 2 to limit /*find odd primes from here on. */ parse var j -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/ if j// 3==0 then iterate /*" " " 3? */ if j// 7==0 then iterate /*" " " 7? */ /* [↑] the above 3 lines saves time.*/ do k=5 while s.k<=j /* [↓] divide by the known odd primes.*/ if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */ end /*k*/ /* [↑] only process numbers ≤ √ J */ #= #+1; @.#= j; s.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */ end /*j*/; return</lang>
- output when using the default inputs:
index │ prime triplets: p, p+2, p+6 are primes, and p < 5,500 ───────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ (5 7 11) (11 13 17) (17 19 23) (41 43 47) 5 │ (101 103 107) (107 109 113) (191 193 197) (227 229 233) 9 │ (311 313 317) (347 349 353) (461 463 467) (641 643 647) 13 │ (821 823 827) (857 859 863) (881 883 887) (1,091 1,093 1,097) 17 │ (1,277 1,279 1,283) (1,301 1,303 1,307) (1,427 1,429 1,433) (1,481 1,483 1,487) 21 │ (1,487 1,489 1,493) (1,607 1,609 1,613) (1,871 1,873 1,877) (1,997 1,999 2,003) 25 │ (2,081 2,083 2,087) (2,237 2,239 2,243) (2,267 2,269 2,273) (2,657 2,659 2,663) 29 │ (2,687 2,689 2,693) (3,251 3,253 3,257) (3,461 3,463 3,467) (3,527 3,529 3,533) 33 │ (3,671 3,673 3,677) (3,917 3,919 3,923) (4,001 4,003 4,007) (4,127 4,129 4,133) 37 │ (4,517 4,519 4,523) (4,637 4,639 4,643) (4,787 4,789 4,793) (4,931 4,933 4,937) 41 │ (4,967 4,969 4,973) (5,231 5,233 5,237) (5,477 5,479 5,483) ───────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 43 prime triplets: p, p+2, p+6 are primes, and p < 5,500
Ring
<lang ring> load "stdlib.ring" see "working..." + nl see "Initial members of prime triples (p, p+2, p+6) are:" + nl see "p p+2 p+6" + nl row = 0 limit = 5500
for n = 1 to limit
if isprime(n) and isprime(n+2) and isprime(n+6) row = row + 1 see "" + n + " " + (n+2) + " " + (n+6) + nl ok
next
see "Found " + row + " primes" + nl see "done..." + nl </lang>
- Output:
working... Initial members of prime triples (p, p+2, p+6) are: p p+2 p+6 5 7 11 11 13 17 17 19 23 41 43 47 101 103 107 107 109 113 191 193 197 227 229 233 311 313 317 347 349 353 461 463 467 641 643 647 821 823 827 857 859 863 881 883 887 1091 1093 1097 1277 1279 1283 1301 1303 1307 1427 1429 1433 1481 1483 1487 1487 1489 1493 1607 1609 1613 1871 1873 1877 1997 1999 2003 2081 2083 2087 2237 2239 2243 2267 2269 2273 2657 2659 2663 2687 2689 2693 3251 3253 3257 3461 3463 3467 3527 3529 3533 3671 3673 3677 3917 3919 3923 4001 4003 4007 4127 4129 4133 4517 4519 4523 4637 4639 4643 4787 4789 4793 4931 4933 4937 4967 4969 4973 5231 5233 5237 5477 5479 5483 Found 43 primes done...
Tiny BASIC
<lang tinybasic> LET A = 1
10 LET A = A + 2 IF A > 5499 THEN END LET P = A GOSUB 100 IF Z = 0 THEN GOTO 10 LET P = A + 2 GOSUB 100 IF Z = 0 THEN GOTO 10 LET P = A + 6 GOSUB 100 IF Z = 0 THEN GOTO 10 PRINT A," ",A+2," ",A+6 GOTO 10
100 REM PRIMALITY BY TRIAL DIVISION
LET Z = 1 LET I = 2
110 IF (P/I)*I = P THEN LET Z = 0
IF Z = 0 THEN RETURN LET I = I + 1 IF I*I <= P THEN GOTO 110 RETURN</lang>
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt
var c = Int.primeSieve(5505, false) var triples = [] System.print("Prime triplets: p, p + 2, p + 6 where p < 5,500:") var i = 3 while (i < 5500) {
if (!c[i] && !c[i+2] && !c[i+6]) triples.add([i, i+2, i+6]) i = i + 2
} for (triple in triples) Fmt.print("$,6d", triple) System.print("\nFound %(triples.count) such prime triplets.")</lang>
- Output:
Prime triplets: p, p + 2, p + 6 where p < 5,500: 5 7 11 11 13 17 17 19 23 41 43 47 101 103 107 107 109 113 191 193 197 227 229 233 311 313 317 347 349 353 461 463 467 641 643 647 821 823 827 857 859 863 881 883 887 1,091 1,093 1,097 1,277 1,279 1,283 1,301 1,303 1,307 1,427 1,429 1,433 1,481 1,483 1,487 1,487 1,489 1,493 1,607 1,609 1,613 1,871 1,873 1,877 1,997 1,999 2,003 2,081 2,083 2,087 2,237 2,239 2,243 2,267 2,269 2,273 2,657 2,659 2,663 2,687 2,689 2,693 3,251 3,253 3,257 3,461 3,463 3,467 3,527 3,529 3,533 3,671 3,673 3,677 3,917 3,919 3,923 4,001 4,003 4,007 4,127 4,129 4,133 4,517 4,519 4,523 4,637 4,639 4,643 4,787 4,789 4,793 4,931 4,933 4,937 4,967 4,969 4,973 5,231 5,233 5,237 5,477 5,479 5,483 Found 43 such prime triplets.