Coprime triplets

Coprime triplets is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

Find and show the smallest number which is coprime to the last two predecessors and has not yet appeared; a(1)=1, a(2)=2.
p and q are coprimes if they have no common factors other than 1.
Let p, q < 50

Factor

Works with: Factor version 0.99 2021-02-05

<lang factor>USING: combinators.short-circuit.smart formatting grouping io kernel make math prettyprint sequences sets ;

coprime? ( m n -- ? ) simple-gcd 1 = ;

coprime-both? ( m n o -- ? ) '[ _ coprime? ] both? ;

triplet? ( hs m n o -- ? )

   { [ coprime-both? nip ] [ 2nip swap in? not ] } && ;

next ( hs m n -- hs' m' n' )

   0 [ 4dup triplet? ] [ 1 + ] until
   nipd pick [ adjoin ] keepd ;

(triplets-upto) ( n -- )

   [ HS{ 1 2 } clone 1 , 1 2 ] dip
   '[ 2dup [ _ < ] both? ] [ dup , next ] while 3drop ;

triplets-upto ( n -- seq ) [ (triplets-upto) ] { } make ;

"Coprime triplets under 50:" print 50 triplets-upto [ 9 group simple-table. nl ] [ length "Found %d terms.\n" printf ] bi</lang>

Output:

Coprime triplets under 50:
1  2  3  5  4  7  9  8  11
13 6  17 19 10 21 23 16 15
29 14 25 27 22 31 35 12 37
41 18 43 47 20 33 49 26 45

Found 36 terms.

FreeBASIC

<lang freebasic>function gcd( a as uinteger, b as uinteger ) as uinteger

   if b = 0 then return a
   return gcd( b, a mod b )

end function

function num_in_array( array() as integer, num as integer ) as boolean

   for i as uinteger = 1 to ubound(array)
       if array(i) = num then return true
   next i
   return false

end function

redim as integer trips(1 to 2) trips(1) = 1 : trips(2) = 2 dim as integer last

do

   last = ubound(trips)
   for q as integer = 1 to 49
       if not num_in_array( trips(), q ) _
         andalso gcd(q, trips(last)) = 1 _
         andalso gcd(q, trips(last-1)) = 1 then
           redim preserve as integer trips( 1 to last+1 )
           trips(last+1) = q
           continue do 
       end if
   next q
   exit do

loop

print using "Found ## terms:"; ubound(trips)

for i as integer = 1 to last

   print trips(i);" ";

next i : print</lang>

Output:

Found 36 terms:
1  2  3  5  4  7  9  8  11  13  6  17  19  10  21  23  16  15  29  14  25  27  22  31  35  12  37  41  18  43  47  20  33  49  26  45

Julia

Translation of: Phix

<lang julia>function coprime_triplets(less_than = 50)

   cpt = [1, 2]
   while true
       m = 1
       while m in cpt || gcd(m, cpt[end]) != 1 || gcd(m, cpt[end - 1]) != 1
           m += 1
       end
       m >= less_than && return cpt
       push!(cpt, m)
   end

end

trps = coprime_triplets() println("Found $(length(trps)) coprime triplets less than 50:") foreach(p -> print(rpad(p[2], 3), p[1] %10 == 0 ? "\n" : ""), enumerate(trps))

</lang>

Output:

Found 36 coprime triplets less than 50:
1  2  3  5  4  7  9  8  11 13 
6  17 19 10 21 23 16 15 29 14
25 27 22 31 35 12 37 41 18 43
47 20 33 49 26 45
</ptw>
=={{header|Phix}}==
<!--<lang Phix>(phixonline)-->

<span style="color: #008080;">function</span> <span style="color: #000000;">coprime_triplets</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">less_than</span><span style="color: #0000FF;">=</span><span style="color: #000000;">50</span><span style="color: #0000FF;">)</span>
    <span style="color: #004080;">sequence</span> <span style="color: #000000;">cpt</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}</span>
    <span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
        <span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
        <span style="color: #008080;">while</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cpt</span><span style="color: #0000FF;">)</span> 
           <span style="color: #008080;">or</span> <span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cpt</span><span style="color: #0000FF;">[$])!=</span><span style="color: #000000;">1</span>
           <span style="color: #008080;">or</span> <span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cpt</span><span style="color: #0000FF;">[$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
            <span style="color: #000000;">m</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
        <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
        <span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">less_than</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
        <span style="color: #000000;">cpt</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">m</span>
    <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
    <span style="color: #008080;">return</span> <span style="color: #000000;">cpt</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">,{{</span><span style="color: #008000;">"%2d"</span><span style="color: #0000FF;">},</span><span style="color: #000000;">coprime_triplets</span><span style="color: #0000FF;">()})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Found %d coprime triplets:\n%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">)})</span>

<!--</lang>-->
{{out}}
<pre>
Found 36 coprime triplets:

1  2  3  5  4  7  9  8 11 13
6 17 19 10 21 23 16 15 29 14

25 27 22 31 35 12 37 41 18 43
47 20 33 49 26 45

Raku

<lang perl6>my @coprime-triplets = 1, 2, {

  state %seen = 1, True, 2, True;
  state $min = 3;
  my $g = $^a * $^b;
  my $n = ($min .. *).first: { !%seen{$_} && ($_ gcd $g == 1) }
  %seen{$n} = True;
  if %seen.elems %% 100 { $min = ($min .. *).first: { !%seen{$_} } }
  $n

} … *;

put "Coprime triplets before first > 50:\n", @coprime-triplets[^(@coprime-triplets.first: * > 50, :k)].batch(10)».fmt("%4d").join: "\n";

put "\nOr maybe, minimum Coprime triplets that encompass 1 through 50:\n", @coprime-triplets[0..(@coprime-triplets.first: * == 42, :k)].batch(10)».fmt("%4d").join: "\n";

put "\nAnd for the heck of it: 1001th through 1050th Coprime triplet:\n", @coprime-triplets[1000..1049].batch(10)».fmt("%4d").join: "\n";</lang>

Output:

Coprime triplets before first > 50:
   1    2    3    5    4    7    9    8   11   13
   6   17   19   10   21   23   16   15   29   14
  25   27   22   31   35   12   37   41   18   43
  47   20   33   49   26   45

Or maybe, minimum Coprime triplets that encompass 1 through 50:
   1    2    3    5    4    7    9    8   11   13
   6   17   19   10   21   23   16   15   29   14
  25   27   22   31   35   12   37   41   18   43
  47   20   33   49   26   45   53   28   39   55
  32   51   59   38   61   63   34   65   57   44
  67   69   40   71   73   24   77   79   30   83
  89   36   85   91   46   75   97   52   81   95
  56   87  101   50   93  103   58   99  107   62
 105  109   64  111  113   68  115  117   74  119
 121   48  125  127   42

And for the heck of it: 1001th through 1050th Coprime triplet:
 682 1293 1361  680 1287 1363  686 1299 1367  688
1305 1369  692 1311 1373  694 1317 1375  698 1323
1381  704 1329 1379  706 1335 1387  716 1341 1385
 712 1347 1391  700 1353 1399  710 1359 1393  718
1371 1397  722 1365 1403  724 1377 1405  728 1383

REXX

<lang rexx>/*REXX program finds and display coprime triplets below a specified limit (limit=50).*/ parse arg n cols . /*obtain optional arguments from the CL*/ if n== | n=="," then n= 50 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ w= max(3, length( commas(n) ) ) /*width of a number in any column. */

                                    @copt= ' coprime triplets  where  N  < '    commas(n)

if cols>0 then say ' index │'center(@copt, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(W+1), '─') !.= 0; @.= !.; idx= 1; $= /*initialize some variables. */

      do #=1
         do j=1;     if @.j  then iterate       /*J in list of coprime triplets?  Skip.*/
         if #<3  then leave                     /*First two entries not defined? Use it*/
                     a= # - 1;    b= # - 2      /*get the last two indices of sequence.*/
         if gcd(j, !.a)\==1  then iterate       /*J not coprime with    last    number?*/
         if gcd(j, !.b)\==1  then iterate       /*"  "     "      "  penultimate   "   */
         leave                                  /*OK, we've found a new coprime triplet*/
         end   /*j*/
      if j>=n  then leave                       /*Have we exceeded the limit? Then quit*/
      @.j= 1;              !.#= j               /*flag a coprime triplet (two methods).*/
      if cols==0  then iterate                  /*Not showing the numbers? Keep looking*/
      $= $  right( commas(j), w)                /*append coprime triplet to output list*/
      if #//cols\==0  then iterate              /*Is output line full? No, keep looking*/
      say center(idx, 7)'│' substr($, 2);    $= /*show output line of coprime triplets.*/
      idx= idx + cols                           /*bump the index for the output line.  */
      end   /*forever*/

if $\== then say center(idx, 7)'│' substr($, 2) /*show any residual output numbers*/ if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─') say say 'Found ' commas(#-1) @copt 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 ? gcd: procedure; parse arg x,y; do until _==0; _= x//y; x= y; y= _; end; return x</lang>

output   when using the default inputs:

 index │    coprime triplets  where  N  <  50
───────┼─────────────────────────────────────────
   1   │   1   2   3   5   4   7   9   8  11  13
  11   │   6  17  19  10  21  23  16  15  29  14
  21   │  25  27  22  31  35  12  37  41  18  43
  31   │  47  20  33  49  26  45
───────┴─────────────────────────────────────────

Found  36  coprime triplets  where  N  <  50

Ring

<lang ring> see "working..." + nl row = 2 numbers = 1:50 first = 1 second = 2 see "Coprime triplets are:" + nl see "" + first + " " + second + " "

    for n = 3 to len(numbers)
        flag1 = 1
        flag2 = 1
        if first < numbers[n]
           min = first
        else
           min = numbers[n]
        ok
        for m = 2 to min
            if first%m = 0 and numbers[n]%m = 0
               flag1 = 0
               exit
            ok
        next
        if second < numbers[n]
           min = second
        else
           min = numbers[n]
        ok
        for m = 2 to min
            if second%m = 0 and numbers[n]%m = 0 
               flag2 = 0
               exit
            ok
        next
        if flag1 = 1 and flag2 = 1
           see "" + numbers[n] + " "
           first = second 
           second = numbers[n] 
           del(numbers,n)
           row = row+1
           if row%10 = 0
              see nl
           ok
           n = 2
        ok
   next

   see nl + "Found " + row + " coprime triplets" + nl
   see "done..." + nl

</lang>

Output:

working...
Coprime triplets are:
1 2 3 5 4 7 9 8 11 13 
6 17 19 10 21 23 16 15 29 14 
25 27 22 31 35 12 37 41 18 43 
47 20 33 49 26 45 
Found 36 coprime triplets
done...

Wren

Translation of: Phix

Library: Wren-math

Library: Wren-seq

Library: Wren-fmt

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

var limit = 50 var cpt = [1, 2]

while (true) {

   var m = 1
   while (cpt.contains(m) || Int.gcd(m, cpt[-1]) != 1 || Int.gcd(m, cpt[-2]) != 1) {
       m = m + 1
   }
   if (m >= limit) break
   cpt.add(m)

} System.print("Coprime triplets under %(limit):") for (chunk in Lst.chunks(cpt, 10)) Fmt.print("$2d", chunk) System.print("\nFound %(cpt.count) such numbers.")</lang>

Output:

Coprime triplets under 50:
 1  2  3  5  4  7  9  8 11 13
 6 17 19 10 21 23 16 15 29 14
25 27 22 31 35 12 37 41 18 43
47 20 33 49 26 45

Found 36 such numbers.