Rosetta Code

Coprime triplets: Difference between revisions

Page Discussion

Coprime triplets (view source)

Revision as of 11:04, 21 November 2023

7,887 bytes added ,  5 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Wren}}: Minor tidy)
 
(11 intermediate revisions by 9 users not shown)
Line 2:
 
;Task:
FindStarting from the sequence a(1)=1 and showa(2)=2 find the next smallest number which is coprime to the last two predecessors and has not yet appeared; a(1)=1,yet a(2)=2in the sequence.
<br>p and q are coprimes if they have no common factors other than 1.
<br> Let '''p, q < 50'''
<br><br>
 
=={{header|11l}}==
{{trans|Nim}}
 
<syntaxhighlight lang="11l">V lst = [1, 2]
 
L
V n = 3
V prev2 = lst[(len)-2]
V prev1 = lst.last
L n C lst | gcd(n, prev2) != 1 | gcd(n, prev1) != 1
n++
I n >= 50
L.break
lst.append(n)
 
print(lst.join(‘ ’))</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
 
=={{header|Action!}}==
<syntaxhighlight lang="action!">INT FUNC Gcd(INT a,b)
INT tmp
 
IF a<b THEN
tmp=a a=b b=tmp
FI
 
WHILE b#0
DO
tmp=a MOD b
a=b b=tmp
OD
RETURN (a)
 
BYTE FUNC Contains(INT v INT ARRAY a INT count)
INT i
 
FOR i=0 TO count-1
DO
IF a(i)=v THEN
RETURN (1)
FI
OD
RETURN (0)
 
BYTE FUNC Skip(INT v INT ARRAY a INT count)
IF Contains(v,a,count) THEN
RETURN (1)
ELSEIF Gcd(v,a(count-1))>1 THEN
RETURN (1)
ELSEIF Gcd(v,a(count-2))>1 THEN
RETURN (1)
FI
RETURN (0)
 
BYTE FUNC CoprimeTriplets(INT limit INT ARRAY a)
INT i,count
 
a(0)=1 a(1)=2
count=2
DO
i=3
WHILE Skip(i,a,count)
DO
i==+1
OD
IF i>=limit THEN
RETURN (count)
FI
a(count)=i
count==+1
OD
RETURN (count)
 
PROC Main()
DEFINE LIMIT="50"
INT ARRAY a(LIMIT)
INT i,count
 
count=CoprimeTriplets(LIMIT,a)
FOR i=0 TO count-1
DO
PrintI(a(i)) Put(32)
OD
PrintF("%E%EThere are %I coprimes less than %I",count,LIMIT)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Coprime_triplets.png Screenshot from Atari 8-bit computer]
<pre>
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
 
There are 36 coprimes less than 50
</pre>
 
=={{header|ALGOL 68}}==
<langsyntaxhighlight lang="algol68">BEGIN # find members of the coprime triplets sequence: starting from 1, 2 the #
# subsequent members are the lowest number coprime to the previous two #
# that haven't appeared in the sequence yet #
Line 61 ⟶ 159:
OD;
print( ( newline, "Found ", whole( printed, 0 ), " coprime triplets up to ", whole( UPB cps, 0 ), newline ) )
END</langsyntaxhighlight>
{{out}}
<pre>
Line 72 ⟶ 170:
 
=={{header|ALGOL W}}==
<langsyntaxhighlight lang="algolw">begin % find a sequence of coprime triplets, each element is coprime to the %
% two predeccessors and hasn't appeared in the list yet, the first two %
% elements are 1 and 2 %
Line 121 ⟶ 219:
end for_i ;
write( i_w := 1, s_w := 0, sCount, " coprime triplets below 50" )
end.</langsyntaxhighlight>
{{out}}
<pre>
Line 132 ⟶ 230:
 
=={{header|AppleScript}}==
<langsyntaxhighlight lang="applescript">on hcf(a, b)
repeat until (b = 0)
set x to a
Line 184 ⟶ 282:
 
-- Task code:
return coprimeTriplets(49)</langsyntaxhighlight>
 
{{output}}
<langsyntaxhighlight lang="applescript">{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}</langsyntaxhighlight>
=={{header|Arturo}}==
 
<langsyntaxhighlight lang="rebol">lst: [1 2]
 
while [true][
Line 208 ⟶ 306:
 
loop split.every:10 lst 'a ->
print map a => [pad to :string & 3]</langsyntaxhighlight>
 
{{out}}
Line 216 ⟶ 314:
25 27 22 31 35 12 37 41 18 43
47 20 33 49 26 45</pre>
 
=={{header|C}}==
<syntaxhighlight lang="c">/*
************************
* *
* COPRIME TRIPLETS *
* *
************************
*/
/* Starting from the sequence a(1)=1 and a(2)=2 find the next smallest number
which is coprime to the last two predecessors and has not yet appeared in the
sequence.
p and q are coprimes if they have no common factors other than 1.
Let p, q < 50 */
 
#include <stdio.h>
 
int Gcd(int v1, int v2)
{
/* It evaluates the Greatest Common Divisor between v1 and v2 */
int a, b, r;
if (v1 < v2)
{
a = v2;
b = v1;
}
else
{
a = v1;
b = v2;
}
do
{
r = a % b;
if (r == 0)
{
break;
}
else
{
a = b;
b = r;
}
} while (1 == 1);
return b;
}
 
int NotInList(int num, int numtrip, int *tripletslist)
{
/* It indicates if the value num is already present in the list tripletslist of length numtrip */
for (int i = 0; i < numtrip; i++)
{
if (num == tripletslist[i])
{
return 0;
}
}
return 1;
}
 
int main()
{
int coprime[50];
int gcd1, gcd2;
int ntrip = 2;
int n = 3;
/* The first two values */
coprime[0] = 1;
coprime[1] = 2;
 
while ( n < 50)
{
gcd1 = Gcd(n, coprime[ntrip-1]);
gcd2 = Gcd(n, coprime[ntrip-2]);
/* if n is coprime of the previous two value
and it isn't already present in the list */
if (gcd1 == 1 && gcd2 == 1 && NotInList(n, ntrip, coprime))
{
coprime[ntrip++] = n;
/* It starts searching a new triplets */
n = 3;
}
else
{
/* Trying to find a triplet with the next value */
n++;
}
}
/* printing the list of coprime triplets */
printf("\n");
for (int i = 0; i < ntrip; i++)
{
printf("%2d ", coprime[i]);
if ((i+1) % 10 == 0)
{
printf("\n");
}
}
printf("\n\nNumber of elements in coprime triplets: %d\n\n", ntrip);
return 0;
}</syntaxhighlight>
 
{{out}}
<pre> 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
 
Number of elements in coprime triplets: 36</pre>
 
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{Trans|Julia}}
<syntaxhighlight lang="delphi">
<lang Delphi>
program Coprime_triplets;
 
Line 275 ⟶ 486:
end;
{$IFNDEF UNIX} Readln; {$ENDIF}
end.</langsyntaxhighlight>
 
=={{header|F_Sharp|F#}}==
<langsyntaxhighlight lang="fsharp">
// Coprime triplets: Nigel Galloway. May 12th., 2021
let rec fN g=function 0->g=1 |n->fN n (g%n)
Line 284 ⟶ 495:
let cT=seq{yield 1; yield 2; yield! fG [1;2] 1 2}
cT|>Seq.takeWhile((>)50)|>Seq.iter(printf "%d "); printfn ""
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 291 ⟶ 502:
=={{header|Factor}}==
{{works with|Factor|0.99 2021-02-05}}
<langsyntaxhighlight lang="factor">USING: combinators.short-circuit.smart formatting grouping io
kernel make math prettyprint sequences sets ;
 
Line 314 ⟶ 525:
50 triplets-upto
[ 9 group simple-table. nl ]
[ length "Found %d terms.\n" printf ] bi</langsyntaxhighlight>
{{out}}
<pre>
Line 327 ⟶ 538:
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">function gcd( a as uinteger, b as uinteger ) as uinteger
if b = 0 then return a
return gcd( b, a mod b )
Line 361 ⟶ 572:
for i as integer = 1 to last
print trips(i);" ";
next i : print</langsyntaxhighlight>
{{out}}
<pre>
Line 371 ⟶ 582:
{{trans|Wren}}
{{libheader|Go-rcu}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 409 ⟶ 620:
}
fmt.Printf("\n\nFound %d such numbers\n", len(cpt))
}</langsyntaxhighlight>
 
{{out}}
Line 423 ⟶ 634:
 
=={{header|Haskell}}==
<langsyntaxhighlight lang="haskell">import Data.List (find, transpose, unfoldr)
import Data.List.Split (chunksOf)
import qualified Data.Set as S
Line 472 ⟶ 683:
 
justifyRight :: Int -> Char -> String -> String
justifyRight n c = (drop . length) <*> (replicate n c <>)</langsyntaxhighlight>
{{Out}}
<pre>36 terms below 50:
Line 486 ⟶ 697:
 
'''Preliminaries'''
<langsyntaxhighlight lang="jq"># jq optimizes the recursive call of _gcd in the following:
def gcd(a;b):
def _gcd:
Line 498 ⟶ 709:
 
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
</syntaxhighlight>
</lang>
'''The task'''
<syntaxhighlight lang="jq">
<lang jq>
# Input: an upper bound greater than 2
# Output: the array of coprime triplets [1,2 ... n] where n is less than the upper bound
Line 515 ⟶ 726:
 
50 | coprime_triplets
| (nwise(10) | map(lpad(2)) | join(" "))</langsyntaxhighlight>
{{out}}
<pre>
Line 525 ⟶ 736:
=={{header|Julia}}==
{{trans|Phix}}
<langsyntaxhighlight lang="julia">function coprime_triplets(less_than = 50)
cpt = [1, 2]
while true
Line 540 ⟶ 751:
println("Found $(length(trps)) coprime triplets less than 50:")
foreach(p -> print(rpad(p[2], 3), p[1] %10 == 0 ? "\n" : ""), enumerate(trps))
</langsyntaxhighlight>{{out}}<pre>
Found 36 coprime triplets less than 50:
1 2 3 5 4 7 9 8 11 13
Line 549 ⟶ 760:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">ClearAll[NextTerm]
NextTerm[a_List] := Module[{pred1, pred2, cands},
{pred1, pred2} = Take[a, -2];
Line 561 ⟶ 772:
]
]
Nest[NextTerm, {1, 2}, 120]</langsyntaxhighlight>
{{out}}
<pre>{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}</pre>
 
=={{header|Nim}}==
<langsyntaxhighlight Nimlang="nim">import math, strutils
 
var list = @[1, 2]
Line 579 ⟶ 790:
list.add n
 
echo list.join(" ")</langsyntaxhighlight>
 
{{out}}
Line 586 ⟶ 797:
=={{header|Perl}}==
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use strict;
use warnings;
use feature <state say>;
Line 609 ⟶ 820:
my @ct;
do { push @ct, $ct->next() } until $ct[-1] > 50; pop @ct;
say join ' ', @ct</langsyntaxhighlight>
{{out}}
<pre>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</pre>
 
=={{header|Phix}}==
<!--<langsyntaxhighlight Phixlang="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>
Line 631 ⟶ 842:
<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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 640 ⟶ 851:
47 20 33 49 26 45
</pre>
 
=={{header|Python}}==
<syntaxhighlight lang="python">
########################
# #
# COPRIME TRIPLETS #
# #
########################
 
#Starting from the sequence a(1)=1 and a(2)=2 find the next smallest number
#which is coprime to the last two predecessors and has not yet appeared in
#the sequence.
#p and q are coprimes if they have no common factors other than 1.
#Let p, q < 50
 
#Function to find the Greatest Common Divisor between v1 and v2
def Gcd(v1, v2):
a, b = v1, v2
if (a < b):
a, b = v2, v1
r = 1
while (r != 0):
r = a % b
if (r != 0):
a = b
b = r
return b
 
#The first two values
a = [1, 2]
#The next value candidate to belong to a triplet
n = 3
 
while (n < 50):
gcd1 = Gcd(n, a[-1])
gcd2 = Gcd(n, a[-2])
#if n is coprime of the previous two value and isn't present in the list
if (gcd1 == 1 and gcd2 == 1 and not(n in a)):
#n is the next element of a triplet
a.append(n)
n = 3
else:
#searching a new triplet with the next value
n += 1
 
#printing the result
for i in range(0, len(a)):
if (i % 10 == 0):
print('')
print("%4d" % a[i], end = '');
 
print("\n\nNumber of elements in coprime triplets = " + str(len(a)), end = "\n")
</syntaxhighlight>
{{out}}
<pre>
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
 
Number of elements in coprime triplets = 36</pre>
 
=={{header|Quackery}}==
 
<code>coprime</code> is defined at [[Coprimes#Quackery]].
 
<syntaxhighlight lang="Quackery"> [ over find swap found not ] is unused ( [ x --> b )
' [ 1 2 ] 2
[ 1+ dup 50 < while
over -1 peek
over coprime until
over -2 peek
over coprime until
2dup unused until
join 2 again ]
drop
echo
</syntaxhighlight>
 
{{out}}
 
<pre>[ 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 ]</pre>
 
=={{header|Raku}}==
<syntaxhighlight lang="raku" perl6line>my @coprime-triplets = 1, 2, {
state %seen = 1, True, 2, True;
state $min = 3;
Line 659 ⟶ 955:
 
put "\nAnd for the heck of it: 1001st through 1050th Coprime triplet:\n",
@coprime-triplets[1000..1049].batch(10)».fmt("%4d").join: "\n";</langsyntaxhighlight>
{{out}}
<pre>Coprime triplets before first > 50:
Line 687 ⟶ 983:
 
=={{header|REXX}}==
<langsyntaxhighlight 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.*/
Line 720 ⟶ 1,016:
/*──────────────────────────────────────────────────────────────────────────────────────*/
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</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
Line 735 ⟶ 1,031:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
see "working..." + nl
row = 2
Line 784 ⟶ 1,080:
see nl + "Found " + row + " coprime triplets" + nl
see "done..." + nl
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 795 ⟶ 1,091:
Found 36 coprime triplets
done...
</pre>
 
=={{header|RPL}}==
{{works with|HP|49g}}
≪ {2 1} → coprimes
≪ '''WHILE''' coprimes HEAD 50 < '''REPEAT'''
coprimes 1 2 SUB
1
'''DO'''
'''DO''' 1 +
'''UNTIL''' coprimes OVER POS NOT '''END'''
'''UNTIL''' DUP2 GCD {1 1} == '''END'''
'coprimes' STO+ DROP
'''END'''
coprimes TAIL REVLIST
≫ ≫ ‘<span style="color:blue">TASK</span>’ STO
{{out}}
<pre>
1: {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}
</pre>
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">list = [1, 2]
available = (1..50).to_a - list
 
Line 804 ⟶ 1,119:
i = available.index{|a| list.last(2).all?{|b| a.gcd(b) == 1}}
break if i.nil?
list << available[.delete_at(i] )
available.delete_at(i)
end
 
puts list.join(" ")
</syntaxhighlight>
</lang>
{{out}}
<pre>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
Line 815 ⟶ 1,129:
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func coprime_triplets(callback) {
 
var (
Line 859 ⟶ 1,173:
coprime_triplets({|list|
list.len == 1050
}).last(50).slices(10).each { .«%« '%4d' -> join(' ').say }</langsyntaxhighlight>
{{out}}
<pre>
Line 891 ⟶ 1,205:
{{trans|Phix}}
{{libheader|Wren-math}}
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">import "./math" for Int
import "./seqfmt" for LstFmt
import "/fmt" for Fmt
 
var limit = 50
Line 909 ⟶ 1,221:
}
System.print("Coprime triplets under %(limit):")
for (chunk in Lst.chunks(cpt, 10)) Fmt.printtprint("$2d", chunkcpt, 10)
System.print("\nFound %(cpt.count) such numbers.")</langsyntaxhighlight>
 
{{out}}
Line 921 ⟶ 1,233:
 
Found 36 such numbers.
</pre>
 
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">func GCD(N, D); \Return the greatest common divisor of N and D
int N, D, R; \numerator and denominator
[if D > N then
[R:= D; D:= N; N:= R]; \swap D and N
while D > 0 do
[R:= rem(N/D);
N:= D;
D:= R;
];
return N;
]; \GCD
 
int A(50), N, I, J;
 
func Used; \Return 'true' if N is in array A
[for J:= 0 to I-1 do
if A(J) = N then return true;
return false;
];
 
[A(0):= 1; A(1):= 2;
Text(0, "1 2 ");
I:= 2;
for N:= 3 to 50-1 do
if not Used and
GCD(A(I-2), N) = 1 and
GCD(A(I-1), N) = 1 then \coprime
[A(I):= N; I:= I+1;
IntOut(0, N); ChOut(0, ^ );
N:= 3;
];
]</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/311865...354778"