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

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

Phix

function coprime_triplets(integer less_than=50)
    sequence cpt = {1,2}
    while true do
        integer m = 1
        while find(m,cpt) 
           or gcd(m,cpt[$])!=1
           or gcd(m,cpt[$-1])!=1 do
            m += 1
        end while
        if m>=less_than then exit end if
        cpt &= m
    end while
    return cpt
end function
sequence res = apply(true,sprintf,{{"%2d"},coprime_triplets()})
printf(1,"Found %d coprime triplets:\n%s\n",{length(res),join_by(res,1,10," ")})

Output:

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;
  sink $^a, $^b;
  my $n = ($min .. *).first: { !%seen{$_} && ($_ gcd $a == 1) && ($_ gcd $b == 1) }
  %seen{$n} = True;
  if %seen.elems %% 300 { $min = ($min .. *).first: { !%seen{$_} } }
  $n   

} … *;

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

put "\n1000th through 1025th Coprime triplet:\n", @coprime-triplets[999..1024].batch(10)».fmt("%4d").join: "\n";</lang>

Output:

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

1000th through 1025th Coprime triplet:
1355  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

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= length( commas(n) ) + 1 /*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 define? Use it.*/
        if gcd(j has(#-1) )\==1 then iterate    /*is J coprime with last number?       */
        if gcd(j has(#-2) )\==1 then iterate    /* " "    "      "  penultimate number?*/
        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 has: parse arg _; return !._</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.