Coprime triplets: Difference between revisions
Thundergnat (talk | contribs) m (→{{header|Raku}}: minor efficiency tweaks) |
(→{{header|REXX}}: added the computer programming language REXX.) |
||
Line 104:
688 1305 1369 692 1311 1373 694 1317 1375 698
1323 1381 704 1329 1379 706</pre>
=={{header|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), '─')
$=; @.=.; idx= 1; $$= /*initialize some variables. */
do #=1
do j=1; if @.j\==. then iterate /*J in list of coprime triplets? Skip.*/
if has(#-1)==.|has(#-2)==. then leave /*1st 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= j; $= $ j /*flag a coprime triplet; add to $ list*/
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 ?
has: procedure expose $; parse arg _; if _<1 then return .; else return word($, _)
/*──────────────────────────────────────────────────────────────────────────────────────*/
gcd: procedure; parse arg $ /*╔═══════════════════════════════════╗*/
do #=2 for arg()-1; $= $ arg(#) /*║This GCD handles multiple arguments║*/
end /*#*/ /*║ & multiple numbers per argument, &║*/
parse var $ x z . /*║negative numbers and non-integers. ║*/
if x=0 then x= z; x= abs(x) /*╚═══════════════════════════════════╝*/
do j=2 to words($); y= abs( word($, j) ); if y=0 then iterate
do until _==0; _= x // y; x= y; y= _
end /*until*/
end /*j*/
return x</lang>
{{out|output|text= when using the default inputs:}}
<pre>
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
</pre>
=={{header|Ring}}==
|
Revision as of 21:01, 28 April 2021
- 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), '─') $=; @.=.; idx= 1; $$= /*initialize some variables. */
do #=1 do j=1; if @.j\==. then iterate /*J in list of coprime triplets? Skip.*/ if has(#-1)==.|has(#-2)==. then leave /*1st 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= j; $= $ j /*flag a coprime triplet; add to $ list*/ 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 ? has: procedure expose $; parse arg _; if _<1 then return .; else return word($, _) /*──────────────────────────────────────────────────────────────────────────────────────*/ gcd: procedure; parse arg $ /*╔═══════════════════════════════════╗*/
do #=2 for arg()-1; $= $ arg(#) /*║This GCD handles multiple arguments║*/ end /*#*/ /*║ & multiple numbers per argument, &║*/ parse var $ x z . /*║negative numbers and non-integers. ║*/ if x=0 then x= z; x= abs(x) /*╚═══════════════════════════════════╝*/ do j=2 to words($); y= abs( word($, j) ); if y=0 then iterate do until _==0; _= x // y; x= y; y= _ end /*until*/ end /*j*/ 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.