Cousin primes: Difference between revisions

Content added Content deleted

Inline

Revision as of 04:40, 19 March 2021

Definitions

In mathematics, cousin primes are prime numbers that differ by four.

For the purposes of this task a cousin prime pair is a pair of non-negative integers of the form [n, n + 4] whose elements are both primes.

Task

Write a program to determine (and show here) all cousin prime pairs whose elements are both less than 1,000.

Optionally, show the number of such pairs.

Also see

the Wikipedia entry: cousin prime.
the OEIS entry: A094343.
the MathWorld entry: cousin primes.

Factor

Works with: Factor version 0.99 2021-02-05

<lang factor>USING: kernel lists lists.lazy math math.primes prettyprint sequences ;

lcousins ( -- list )

   L{ { 3 7 } } 7 11 [ [ 6 + ] lfrom-by ] bi@ lzip lappend-lazy
   [ [ prime? ] all? ] lfilter ;

lcousins [ last 1000 < ] lwhile [ . ] leach</lang>

Output:

{ 3 7 }
{ 7 11 }
{ 13 17 }
{ 19 23 }
{ 37 41 }
{ 43 47 }
{ 67 71 }
{ 79 83 }
{ 97 101 }
{ 103 107 }
{ 109 113 }
{ 127 131 }
{ 163 167 }
{ 193 197 }
{ 223 227 }
{ 229 233 }
{ 277 281 }
{ 307 311 }
{ 313 317 }
{ 349 353 }
{ 379 383 }
{ 397 401 }
{ 439 443 }
{ 457 461 }
{ 463 467 }
{ 487 491 }
{ 499 503 }
{ 613 617 }
{ 643 647 }
{ 673 677 }
{ 739 743 }
{ 757 761 }
{ 769 773 }
{ 823 827 }
{ 853 857 }
{ 859 863 }
{ 877 881 }
{ 883 887 }
{ 907 911 }
{ 937 941 }
{ 967 971 }

Julia

Translation of: Wren

<lang julia>using Primes

let

   p = primesmask(1000)
   println("Cousin prime pairs under 1,000:")
   pcount = 0
   for i in 2:996
       if p[i] && p[i + 4]
           pcount += 1
           print(lpad(i, 4), ":", rpad(i + 4, 4), pcount % 8 == 0 ? "\n" : "")
       end
   end
   println("\n\n$pcount pairs found.")

end

</lang>

Output:

Cousin prime pairs under 1,000:
   3:7      7:11    13:17    19:23    37:41    43:47    67:71    79:83
  97:101  103:107  109:113  127:131  163:167  193:197  223:227  229:233
 277:281  307:311  313:317  349:353  379:383  397:401  439:443  457:461
 463:467  487:491  499:503  613:617  643:647  673:677  739:743  757:761
 769:773  823:827  853:857  859:863  877:881  883:887  907:911  937:941
 967:971

41 pairs found.

Pascal

This example is incorrect. Please fix the code and remove this message.

Details: wrong output, syntax error on fpc

Works with: Free Pascal

Works with: Delphi

Sieving only odd numbers.

<lang pascal>program Cousin_primes; //Free Pascal Compiler version 3.2.1 [2020/11/03] for x86_64fpc {$IFDEF FPC}

 {$MODE DELPHI}
 {$Optimization ON,ALL}

const

 ERROR_SPACE = -243;
 MAXZAHL = 1000;// > 3
 MAXLIMIT = (MAXZAHL-1) DIV 2;
 //estimate
 CountOfPrimes = trunc(MAXZAHL/(ln(MAXZAHL)-1.08))+100;

type

 tChkprimes = array[0..MAXLIMIT] of byte;//prime == 1 , nonprime == 0
 tPrimes: array[0..CountOfPrimes]of Uint32;

{$ELSE}

 {$APPTYPE CONSOLE}

const

 ERROR_SPACE = 243;
 MAXZAHL = 1000;// > 3
 MAXLIMIT = (MAXZAHL-1) DIV 2;

type

 tChkprimes = array of byte;
 tPrimes = array of Uint32;

var

CountOfPrimes:  Uint32;

{$ENDIF}

var

 Chkprimes:tChkprimes;
 primes :tPrimes; //here starting with 3
 primeCount:NativeInt;

procedure InitPrimes; //sieve of eratothenes var

 i,j : NativeInt;

begin

 // i = 2*j+1

{$IFDEF FPC}

 fillchar(Chkprimes,SizeOf(tChkprimes),#1);

{$ELSE}

 fillchar(Chkprimes[0],length(Chkprimes),#1);

{$ENDIF}

 Chkprimes[0] := 0;
 i := 1;
 repeat
   if Chkprimes[(i-1) DIV 2] <> 0 then
   Begin
     j := (i*i-1) DIV 2;
     if j> MAXLIMIT then
       break;
     repeat
       Chkprimes[j]:= 0;
       inc(j,i);
     until j> MAXLIMIT;
   end;
   inc(i,2);
 until false;

 j := 0;
 For i := 1 to MAXLIMIT do
   IF Chkprimes[i]<>0 then
   Begin
     primes[j] := 2*i+1;
     inc(j);
   end;

// writeln('prime count ',j+1,' til ',MAXZAHL); //count "2"

 primeCount := j-1;

 IF CountOfPrimes-primeCount < 0 then
 begin
   writeln(' Need more space for primes ', primeCount-CountOfPrimes);
   HALT(ERROR_SPACE);
 end;

end; var

 i,cnt : NativeInt;

BEGIN {$IFNDEF FPC}

  CountOfPrimes := trunc(MAXZAHL/(ln(MAXZAHL)-1.08))+100;
  SetLength(primes,CountOfPrimes+1);
  SetLength(Chkprimes,CountOfPrimes+1);

{$ENDIF}

 InitPrimes;
 //only exception, that the index difference is greater 1
write(primes[0]:3,':',primes[2]:3,' ');
 cnt := 1;
 For i := 1 to primeCount do
   IF primes[i]-primes[i-1] = 4 then
   Begin
     write(primes[i-1]:3,':',primes[i]:3,' ');
     inc(cnt);
     If cnt MOD 6 = 0 then
       writeln;
   end;
 writeln;
 writeln(cnt,' cousin primes found');

END. </lang>

Output:

  3:  7   7: 11  13: 17  19: 23  37: 41  43: 47
 67: 71  79: 83  97:101 103:107 109:113 127:131
163:167 193:197 223:227 229:233 277:281 307:311
313:317 349:353 379:383 397:401 439:443 457:461
463:467 487:491 499:503
27 cousin primes found

Phix

<lang Phix>function has_cousin(integer p) return is_prime(p+4) end function for n=2 to 7 do

   integer tn = power(10,n)
   sequence res = filter(get_primes_le(tn-9),has_cousin)
   res = columnize({res,sq_add(res,4)})
   printf(1,"%,d cousin prime pairs less than %,d found: %v\n",{length(res),tn,shorten(res,"",min(4,5-floor(n/2)))})

end for</lang> (Uses tn-9 instead of the more obvious tn-4 since none of 96,95,94,93,92 or similar could ever be prime. Note that {97,101} is deliberately excluded from < 100.)

Output:

8 cousin prime pairs less than 100 found: {{3,7},{7,11},{13,17},{19,23},{37,41},{43,47},{67,71},{79,83}}
41 cousin prime pairs less than 1,000 found: {{3,7},{7,11},{13,17},{19,23},"...",{883,887},{907,911},{937,941},{967,971}}
203 cousin prime pairs less than 10,000 found: {{3,7},{7,11},{13,17},"...",{9787,9791},{9829,9833},{9883,9887}}
1,216 cousin prime pairs less than 100,000 found: {{3,7},{7,11},{13,17},"...",{99709,99713},{99829,99833},{99877,99881}}
8,144 cousin prime pairs less than 1,000,000 found: {{3,7},{7,11},"...",{999769,999773},{999979,999983}}
58,622 cousin prime pairs less than 10,000,000 found: {{3,7},{7,11},"...",{9999217,9999221},{9999397,9999401}}

This REXX version allows the limit to be specified, as well as the number of cousin prime pairs to be shown per line. <lang rexx>/*REXX program counts the number of twin prime pairs under a specified number N. */ parse arg n cols . /*get optional number of primes to find*/ if n== | n=="," then n= 1000 /*Not specified? Then assume default.*/ if cols== | cols=="," then cols= 10 /*Not specified? Then assume default.*/ call genP n-1 /*generate all primes under N. */ pairs= 0; dups= 0 /*initialize # cousin prime pairs; dups*/ dups= 0 /*the number of duplicate cousin primes*/ $= /*a list of cousin prime pairs (so far)*/

      do j=1  while @.j\==.;  c= @.j - 4        /*lets hunt for cousin prime pairs.    */
      if \!.c  then iterate                     /*Not a lowe cousin pair? Then skip it.*/
      $= $ ' ('@.j-4","@.j')'; pairs= pairs + 1 /*add cousin pair to the list.         */
      if @.j==11          then dups= dups + 1   /*take care to note if there is a dup. */
      if pairs//cols\==0  then iterate          /*have we populated a line of output?  */
      say strip($);            $=               /*display what we have so far  (cols). */
      end   /*j*/

if $\== then say strip($) /*possible display some residual output*/ say say 'found ' pairs " cousin prime pairs." say 'found ' pairs*2-dups " unique cousin primes." exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: parse arg n; @.=.; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; @.7=17; #= 7

                   !.=0; !.2=1;  !.3=1;  !.5=1;  !.7=1;  !.11=1;  !.13=1;  !.17=1
           do j=@.7+2  by 2  while j<=n         /*continue on with the next odd prime. */
           parse var  j    -1  _              /*obtain the last digit of the  J  var.*/
           if _      ==5  then iterate          /*is this integer a multiple of five?  */
           if j // 3 ==0  then iterate          /* "   "     "    "     "     " three? */
                                                /* [↓]  divide by the primes.   ___    */
                 do k=4  to #  while  k*k<=j    /*divide  J  by other primes ≤ √ J     */
                 if j//@.k == 0  then iterate j /*÷ by prev. prime?  ¬prime     ___    */
                 end   /*k*/                    /* [↑]   only divide up to     √ J     */
           #= # + 1;          @.#= j;  !.j= 1   /*bump prime count; assign prime & flag*/
           end   /*j*/
    return</lang>

output when using the default inputs:

(3,7)  (7,11)  (13,17)  (19,23)  (37,41)  (43,47)  (67,71)  (79,83)  (97,101)  (103,107)
(109,113)  (127,131)  (163,167)  (193,197)  (223,227)  (229,233)  (277,281)  (307,311)  (313,317)  (349,353)
(379,383)  (397,401)  (439,443)  (457,461)  (463,467)  (487,491)  (499,503)  (613,617)  (643,647)  (673,677)
(739,743)  (757,761)  (769,773)  (823,827)  (853,857)  (859,863)  (877,881)  (883,887)  (907,911)  (937,941)
(967,971)

found  41  cousin prime pairs.
found  81  unique cousin primes.

Raku

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 { $_, $_+4 }, 2..999;</lang>

Output:

((3 7) (7 11) (13 17) (19 23) (37 41) (43 47) (67 71) (79 83) (97 101) (103 107) (109 113) (127 131) (163 167) (193 197) (223 227) (229 233) (277 281) (307 311) (313 317) (349 353) (379 383) (397 401) (439 443) (457 461) (463 467) (487 491) (499 503) (613 617) (643 647) (673 677) (739 743) (757 761) (769 773) (823 827) (853 857) (859 863) (877 881) (883 887) (907 911) (937 941) (967 971))

Infinite List

A more efficient and versatile approach is to generate an infinite list of cousin primes, using this info from https://oeis.org/A023200 :

Apart from the first term, all terms are of the form 6n + 1.

<lang perl6>constant @cousins = (3, 7, *+6 … *).map: -> \n { (n, n+4) if (n & n+4).is-prime };

my $count = @cousins.first: :k, *.[0] > 1000;

.say for @cousins.head($count).batch(9);</lang>

Output:

((3 7) (7 11) (13 17) (19 23) (37 41) (43 47) (67 71) (79 83) (97 101))
((103 107) (109 113) (127 131) (163 167) (193 197) (223 227) (229 233) (277 281) (307 311))
((313 317) (349 353) (379 383) (397 401) (439 443) (457 461) (463 467) (487 491) (499 503))
((613 617) (643 647) (673 677) (739 743) (757 761) (769 773) (823 827) (853 857) (859 863))
((877 881) (883 887) (907 911) (937 941) (967 971))

Wren

Library: Wren-math

Library: Wren-fmt

<lang ecmascript>import "/math" for Int import "/fmt" for Fmt

var c = Int.primeSieve(999, false) var count = 0 System.print("Cousin prime pairs whose elements are less than 1,000:") var i = 3 while (i <= 995) {

   if (!c[i] && !c[i + 4]) {
       Fmt.write("$3d:$3d  ", i, i + 4)
       count = count + 1
       if ((count % 7) == 0) System.print()
       i = (i != 3) ? i + 4 : i + 2
   }
   i = i + 2

} System.print("\n\n%(count) pairs found")</lang>

Output:

Cousin prime pairs whose elements are less than 1,000:
  3:  7    7: 11   13: 17   19: 23   37: 41   43: 47   67: 71  
 79: 83   97:101  103:107  109:113  127:131  163:167  193:197  
223:227  229:233  277:281  307:311  313:317  349:353  379:383  
397:401  439:443  457:461  463:467  487:491  499:503  613:617  
643:647  673:677  739:743  757:761  769:773  823:827  853:857  
859:863  877:881  883:887  907:911  937:941  967:971  

41 pairs found

Ring

<lang ring> load "stdlib.ring"

see "working..." + nl see "cousin primes are:" + nl

ind = 0 row = 0 limit = 1000

for n = 1 to limit

   if isprime(n) and isprime(n+4)
      row = row + 1
      ind1 = find(cousin,n)
      ind2 = find(cousin,n+4)
      if ind1 < 1
         add(cousin,n)
      ok
      if ind2 < 1
         add(cousin,n+4)
      ok  
      see "(" + n + ", " + (n+4) + ") "
         if row%5 = 0
            see nl
         ok
   ok

Output:

working...
cousin primes are:
(3, 7) (7, 11) (13, 17) (19, 23) (37, 41) 
(43, 47) (67, 71) (79, 83) (97, 101) (103, 107) 
(109, 113) (127, 131) (163, 167) (193, 197) (223, 227) 
(229, 233) (277, 281) (307, 311) (313, 317) (349, 353) 
(379, 383) (397, 401) (439, 443) (457, 461) (463, 467) 
(487, 491) (499, 503) (613, 617) (643, 647) (673, 677) 
(739, 743) (757, 761) (769, 773) (823, 827) (853, 857) 
(859, 863) (877, 881) (883, 887) (907, 911) (937, 941) 
(967, 971) 
found 41 cousin prime pairs.
found 81 unique cousin primes.
done...