Coprime triplets
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
- Task
Factor
<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
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= 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
<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.