Coprime triplets: Difference between revisions
Content added Content deleted
m (→{{header|Wren}}: Minor tidy) |
|||
(31 intermediate revisions by 20 users not shown) | |||
Line 2: | Line 2: | ||
;Task: |
;Task: |
||
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 yet in the sequence. |
|||
<br>p and q are coprimes if they have no common factors other than 1. |
<br>p and q are coprimes if they have no common factors other than 1. |
||
<br> Let '''p, q < 50''' |
<br> Let '''p, q < 50''' |
||
<br><br> |
<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}}== |
|||
<syntaxhighlight 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 # |
|||
# iterative Greatest Common Divisor routine, returns the gcd of m and n # |
|||
PROC gcd = ( INT m, n )INT: |
|||
BEGIN |
|||
INT a := ABS m, b := ABS n; |
|||
WHILE b /= 0 DO |
|||
INT new a = b; |
|||
b := a MOD b; |
|||
a := new a |
|||
OD; |
|||
a |
|||
END # gcd # ; |
|||
# returns an array of the coprime triplets up to n # |
|||
OP COPRIMETRIPLETS = ( INT n )[]INT: |
|||
BEGIN |
|||
[ 1 : n ]INT result; |
|||
IF n > 0 THEN |
|||
result[ 1 ] := 1; |
|||
IF n > 1 THEN |
|||
[ 1 : n ]BOOL used; |
|||
used[ 1 ] := used[ 2 ] := TRUE; |
|||
FOR i FROM 3 TO n DO used[ i ] := FALSE; result[ i ] := 0 OD; |
|||
result[ 2 ] := 2; |
|||
FOR i FROM 3 TO n DO |
|||
INT p1 = result[ i - 1 ]; |
|||
INT p2 = result[ i - 2 ]; |
|||
BOOL found := FALSE; |
|||
FOR j TO n WHILE NOT found DO |
|||
IF NOT used[ j ] THEN |
|||
found := gcd( p1, j ) = 1 AND gcd( p2, j ) = 1; |
|||
IF found THEN |
|||
used[ j ] := TRUE; |
|||
result[ i ] := j |
|||
FI |
|||
FI |
|||
OD |
|||
OD |
|||
FI |
|||
FI; |
|||
result |
|||
END # COPRIMETRIPLETS # ; |
|||
[]INT cps = COPRIMETRIPLETS 49; |
|||
INT printed := 0; |
|||
FOR i TO UPB cps DO |
|||
IF cps[ i ] /= 0 THEN |
|||
print( ( whole( cps[ i ], -3 ) ) ); |
|||
printed +:= 1; |
|||
IF printed MOD 10 = 0 THEN print( ( newline ) ) FI |
|||
FI |
|||
OD; |
|||
print( ( newline, "Found ", whole( printed, 0 ), " coprime triplets up to ", whole( UPB cps, 0 ), newline ) ) |
|||
END</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 |
|||
Found 36 coprime triplets up to 49 |
|||
</pre> |
|||
=={{header|ALGOL W}}== |
|||
<syntaxhighlight 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 % |
|||
integer procedure gcd ( integer value m, n ) ; |
|||
begin |
|||
integer a, b; |
|||
a := abs m; |
|||
b := abs n; |
|||
while b not = 0 do begin |
|||
integer newA; |
|||
newA := b; |
|||
b := a rem b; |
|||
a := newA |
|||
end while_b_ne_0 ; |
|||
a |
|||
end gcd ; |
|||
% construct the sequence % |
|||
integer array seq ( 1 :: 49 ); |
|||
integer sCount; |
|||
seq( 1 ) := 1; seq( 2 ) := 2; for i := 3 until 49 do seq( i ) := 0; |
|||
for i := 3 until 49 do begin |
|||
integer s1, s2, lowest; |
|||
s1 := seq( i - 1 ); |
|||
s2 := seq( i - 2 ); |
|||
lowest := 2; |
|||
while begin logical candidate; |
|||
lowest := lowest + 1; |
|||
candidate := gcd( s1, lowest ) = 1 and gcd( s2, lowest ) = 1; |
|||
if candidate then begin |
|||
% lowest is coprime to the previous two elements % |
|||
% check it hasn't appeared already % |
|||
for pos := 1 until i - 1 do begin |
|||
candidate := candidate and lowest not = seq( pos ); |
|||
end for_pos ; |
|||
if candidate then seq( i ) := lowest; |
|||
end if_lowest_coprime_to_s1_and_s2 ; |
|||
not candidate and lowest < 50 |
|||
end do begin end while_not_found |
|||
end for_i ; |
|||
% show the sequence % |
|||
sCount := 0; |
|||
for i := 1 until 49 do begin |
|||
if seq( i ) not = 0 then begin |
|||
writeon( i_w := 2, s_w := 0, " ", seq( i ) ); |
|||
sCount := sCount + 1; |
|||
if sCount rem 10 = 0 then write() |
|||
end if_seq_i_ne_0 |
|||
end for_i ; |
|||
write( i_w := 1, s_w := 0, sCount, " coprime triplets below 50" ) |
|||
end.</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 |
|||
36 coprime triplets below 50 |
|||
</pre> |
|||
=={{header|AppleScript}}== |
|||
<syntaxhighlight lang="applescript">on hcf(a, b) |
|||
repeat until (b = 0) |
|||
set x to a |
|||
set a to b |
|||
set b to x mod b |
|||
end repeat |
|||
if (a < 0) then return -a |
|||
return a |
|||
end hcf |
|||
on coprimeTriplets(max) |
|||
if (max < 3) then return {} |
|||
script o |
|||
property candidates : {} |
|||
property output : {1, 2} |
|||
end script |
|||
-- When repeatedly searching for lowest unused numbers, it's faster in |
|||
-- AppleScript to take numbers from a preset list of candidates which |
|||
-- grows shorter from at or near the low end as used numbers are removed |
|||
-- than it is to test increasing numbers of previous numbers each time |
|||
-- against a list that's growing longer with them. |
|||
-- Generate the list of candidates here. |
|||
repeat with i from 3 to max |
|||
set end of o's candidates to i |
|||
end repeat |
|||
set candidateCount to max - 2 |
|||
set {p1, p2} to o's output |
|||
set ok to true |
|||
repeat while (ok) -- While suitable coprimes found and candidates left. |
|||
repeat with i from 1 to candidateCount |
|||
set q to item i of o's candidates |
|||
set ok to ((hcf(p1, q) is 1) and (hcf(p2, q) is 1)) |
|||
if (ok) then -- q is coprime with both p1 and p2. |
|||
set end of o's output to q |
|||
set p1 to p2 |
|||
set p2 to q |
|||
-- Remove q from the candidate list. |
|||
set item i of o's candidates to missing value |
|||
set o's candidates to o's candidates's numbers |
|||
set candidateCount to candidateCount - 1 |
|||
set ok to (candidateCount > 0) |
|||
exit repeat |
|||
end if |
|||
end repeat |
|||
end repeat |
|||
return o's output |
|||
end coprimeTriplets |
|||
-- Task code: |
|||
return coprimeTriplets(49)</syntaxhighlight> |
|||
{{output}} |
|||
<syntaxhighlight 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}</syntaxhighlight> |
|||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="rebol">lst: [1 2] |
|||
while [true][ |
|||
n: 3 |
|||
prev2: lst\[dec dec size lst] |
|||
prev1: last lst |
|||
while -> any? @[ |
|||
contains? lst n |
|||
1 <> gcd @[n prev2] |
|||
1 <> gcd @[n prev1] |
|||
] -> n: n + 1 |
|||
if n >= 50 -> break |
|||
'lst ++ n |
|||
] |
|||
loop split.every:10 lst 'a -> |
|||
print map a => [pad to :string & 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> |
|||
=={{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"> |
|||
program Coprime_triplets; |
|||
{$APPTYPE CONSOLE} |
|||
uses |
|||
System.SysUtils; |
|||
//https://rosettacode.org/wiki/Greatest_common_divisor#Pascal_.2F_Delphi_.2F_Free_Pascal |
|||
function Gcd(u, v: longint): longint; |
|||
begin |
|||
if v = 0 then |
|||
EXIT(u); |
|||
result := Gcd(v, u mod v); |
|||
end; |
|||
function IsIn(value: Integer; a: TArray<Integer>): boolean; |
|||
begin |
|||
for var e in a do |
|||
if e = value then |
|||
exit(true); |
|||
Result := false; |
|||
end; |
|||
function CoprimeTriplets(less_than: Integer = 50): TArray<Integer>; |
|||
var |
|||
cpt: TArray<Integer>; |
|||
_end: Integer; |
|||
begin |
|||
cpt := [1, 2]; |
|||
_end := high(cpt); |
|||
while True do |
|||
begin |
|||
var m := 1; |
|||
while IsIn(m, cpt) or (gcd(m, cpt[_end]) <> 1) or (gcd(m, cpt[_end - 1]) <> 1) do |
|||
inc(m); |
|||
if m >= less_than then |
|||
exit(cpt); |
|||
SetLength(cpt, Length(cpt) + 1); |
|||
_end := high(cpt); |
|||
cpt[_end] := m; |
|||
end; |
|||
end; |
|||
begin |
|||
var trps := CoprimeTriplets(); |
|||
writeln('Found ', length(trps), ' coprime triplets less than 50:'); |
|||
for var i := 0 to High(trps) do |
|||
begin |
|||
write(trps[i]: 2, ' '); |
|||
if (i + 1) mod 10 = 0 then |
|||
writeln; |
|||
end; |
|||
{$IFNDEF UNIX} Readln; {$ENDIF} |
|||
end.</syntaxhighlight> |
|||
=={{header|F_Sharp|F#}}== |
|||
<syntaxhighlight lang="fsharp"> |
|||
// Coprime triplets: Nigel Galloway. May 12th., 2021 |
|||
let rec fN g=function 0->g=1 |n->fN n (g%n) |
|||
let rec fG t n1 n2=seq{let n=seq{1..0x0FFFFFFF}|>Seq.find(fun n->not(List.contains n t) && fN n1 n && fN n2 n) in yield n; yield! cT(n::t) n2 n} |
|||
let cT=seq{yield 1; yield 2; yield! fG [1;2] 1 2} |
|||
cT|>Seq.takeWhile((>)50)|>Seq.iter(printf "%d "); printfn "" |
|||
</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|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.99 2021-02-05}} |
{{works with|Factor|0.99 2021-02-05}} |
||
< |
<syntaxhighlight lang="factor">USING: combinators.short-circuit.smart formatting grouping io |
||
kernel make math prettyprint sequences sets ; |
kernel make math prettyprint sequences sets ; |
||
Line 32: | Line 525: | ||
50 triplets-upto |
50 triplets-upto |
||
[ 9 group simple-table. nl ] |
[ 9 group simple-table. nl ] |
||
[ length "Found %d terms.\n" printf ] bi</ |
[ length "Found %d terms.\n" printf ] bi</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 45: | Line 538: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">function gcd( a as uinteger, b as uinteger ) as uinteger |
||
if b = 0 then return a |
if b = 0 then return a |
||
return gcd( b, a mod b ) |
return gcd( b, a mod b ) |
||
Line 79: | Line 572: | ||
for i as integer = 1 to last |
for i as integer = 1 to last |
||
print trips(i);" "; |
print trips(i);" "; |
||
next i : print</ |
next i : print</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 86: | Line 579: | ||
</pre> |
</pre> |
||
=={{header|Go}}== |
|||
{{trans|Wren}} |
|||
{{libheader|Go-rcu}} |
|||
<syntaxhighlight lang="go">package main |
|||
import ( |
|||
"fmt" |
|||
"rcu" |
|||
) |
|||
func contains(a []int, v int) bool { |
|||
for _, e := range a { |
|||
if e == v { |
|||
return true |
|||
} |
|||
} |
|||
return false |
|||
} |
|||
func main() { |
|||
const limit = 50 |
|||
cpt := []int{1, 2} |
|||
for { |
|||
m := 1 |
|||
l := len(cpt) |
|||
for contains(cpt, m) || rcu.Gcd(m, cpt[l-1]) != 1 || rcu.Gcd(m, cpt[l-2]) != 1 { |
|||
m++ |
|||
} |
|||
if m >= limit { |
|||
break |
|||
} |
|||
cpt = append(cpt, m) |
|||
} |
|||
fmt.Printf("Coprime triplets under %d:\n", limit) |
|||
for i, t := range cpt { |
|||
fmt.Printf("%2d ", t) |
|||
if (i+1)%10 == 0 { |
|||
fmt.Println() |
|||
} |
|||
} |
|||
fmt.Printf("\n\nFound %d such numbers\n", len(cpt)) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Haskell}}== |
|||
<syntaxhighlight lang="haskell">import Data.List (find, transpose, unfoldr) |
|||
import Data.List.Split (chunksOf) |
|||
import qualified Data.Set as S |
|||
--------------------- COPRIME TRIPLES -------------------- |
|||
coprimeTriples :: Integral a => [a] |
|||
coprimeTriples = |
|||
[1, 2] <> unfoldr go (S.fromList [1, 2], (1, 2)) |
|||
where |
|||
go (seen, (a, b)) = |
|||
Just |
|||
(c, (S.insert c seen, (b, c))) |
|||
where |
|||
Just c = |
|||
find |
|||
( ((&&) . flip S.notMember seen) |
|||
<*> ((&&) . coprime a <*> coprime b) |
|||
) |
|||
[3 ..] |
|||
coprime :: Integral a => a -> a -> Bool |
|||
coprime a b = 1 == gcd a b |
|||
--------------------------- TEST ------------------------- |
|||
main :: IO () |
|||
main = |
|||
let xs = takeWhile (< 50) coprimeTriples |
|||
in putStrLn (show (length xs) <> " terms below 50:\n") |
|||
>> putStrLn |
|||
( spacedTable |
|||
justifyRight |
|||
(chunksOf 10 (show <$> xs)) |
|||
) |
|||
-------------------------- FORMAT ------------------------ |
|||
spacedTable :: |
|||
(Int -> Char -> String -> String) -> [[String]] -> String |
|||
spacedTable aligned rows = |
|||
unlines $ |
|||
unwords |
|||
. zipWith |
|||
(`aligned` ' ') |
|||
(maximum . fmap length <$> transpose rows) |
|||
<$> rows |
|||
justifyRight :: Int -> Char -> String -> String |
|||
justifyRight n c = (drop . length) <*> (replicate n c <>)</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>36 terms below 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</pre> |
|||
=={{header|jq}}== |
|||
{{works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
'''Preliminaries''' |
|||
<syntaxhighlight lang="jq"># jq optimizes the recursive call of _gcd in the following: |
|||
def gcd(a;b): |
|||
def _gcd: |
|||
if .[1] != 0 then [.[1], .[0] % .[1]] | _gcd else .[0] end; |
|||
[a,b] | _gcd ; |
|||
# Pretty-printing |
|||
def nwise($n): |
|||
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end; |
|||
n; |
|||
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .; |
|||
</syntaxhighlight> |
|||
'''The task''' |
|||
<syntaxhighlight 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 |
|||
def coprime_triplets: |
|||
. as $less_than |
|||
| {cpt: [1, 2], m:0} |
|||
| until( .m >= $less_than; |
|||
.m = 1 |
|||
| .cpt as $cpt |
|||
| until( (.m | IN($cpt[]) | not) and (gcd(.m; $cpt[-1]) == 1) and (gcd(.m; $cpt[-2]) == 1); |
|||
.m += 1 ) |
|||
| .cpt = $cpt + [.m] ) |
|||
| .cpt[:-1]; |
|||
50 | coprime_triplets |
|||
| (nwise(10) | map(lpad(2)) | 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|Julia}}== |
=={{header|Julia}}== |
||
{{trans|Phix}} |
{{trans|Phix}} |
||
< |
<syntaxhighlight lang="julia">function coprime_triplets(less_than = 50) |
||
cpt = [1, 2] |
cpt = [1, 2] |
||
while true |
while true |
||
Line 103: | Line 751: | ||
println("Found $(length(trps)) coprime triplets less than 50:") |
println("Found $(length(trps)) coprime triplets less than 50:") |
||
foreach(p -> print(rpad(p[2], 3), p[1] %10 == 0 ? "\n" : ""), enumerate(trps)) |
foreach(p -> print(rpad(p[2], 3), p[1] %10 == 0 ? "\n" : ""), enumerate(trps)) |
||
</ |
</syntaxhighlight>{{out}}<pre> |
||
Found 36 coprime triplets less than 50: |
Found 36 coprime triplets less than 50: |
||
1 2 3 5 4 7 9 8 11 13 |
1 2 3 5 4 7 9 8 11 13 |
||
Line 110: | Line 758: | ||
47 20 33 49 26 45 |
47 20 33 49 26 45 |
||
</pre> |
</pre> |
||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">ClearAll[NextTerm] |
|||
NextTerm[a_List] := Module[{pred1, pred2, cands}, |
|||
{pred1, pred2} = Take[a, -2]; |
|||
cands = |
|||
Select[Range[50], CoprimeQ[#, pred1] && CoprimeQ[#, pred2] &]; |
|||
cands = Complement[cands, a]; |
|||
If[Length[cands] > 0, |
|||
Append[a, First[cands]] |
|||
, |
|||
a |
|||
] |
|||
] |
|||
Nest[NextTerm, {1, 2}, 120]</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|Nim}}== |
|||
<syntaxhighlight lang="nim">import math, strutils |
|||
var list = @[1, 2] |
|||
while true: |
|||
var n = 3 |
|||
let prev2 = list[^2] |
|||
let prev1 = list[^1] |
|||
while n in list or gcd(n, prev2) != 1 or gcd(n, prev1) != 1: |
|||
inc n |
|||
if n >= 50: break |
|||
list.add n |
|||
echo list.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|Perl}}== |
|||
{{libheader|ntheory}} |
|||
<syntaxhighlight lang="perl">use strict; |
|||
use warnings; |
|||
use feature <state say>; |
|||
use ntheory 'gcd'; |
|||
use List::Util 'first'; |
|||
use List::Lazy 'lazy_list'; |
|||
use enum qw(False True); |
|||
use constant Inf => 1e5; |
|||
my $ct = lazy_list { |
|||
state @c = (1, 2); |
|||
state %seen = (1 => True, 2 => True); |
|||
state $min = 3; |
|||
my $g = $c[-2] * $c[-1]; |
|||
my $n = first { !$seen{$_} and gcd($_,$g) == 1 } $min .. Inf; |
|||
$seen{$n} = True; |
|||
$min = first { !$seen{$_} } $min .. Inf; |
|||
push @c, $n; |
|||
shift @c |
|||
}; |
|||
my @ct; |
|||
do { push @ct, $ct->next() } until $ct[-1] > 50; pop @ct; |
|||
say join ' ', @ct</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|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight 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: #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: #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 129: | Line 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: #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> |
<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> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 138: | Line 851: | ||
47 20 33 49 26 45 |
47 20 33 49 26 45 |
||
</pre> |
</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}}== |
=={{header|Raku}}== |
||
<lang |
<syntaxhighlight lang="raku" line>my @coprime-triplets = 1, 2, { |
||
state %seen = 1, True, 2, True; |
state %seen = 1, True, 2, True; |
||
state $min = 3; |
state $min = 3; |
||
Line 156: | Line 954: | ||
@coprime-triplets[0..(@coprime-triplets.first: * == 42, :k)].batch(10)».fmt("%4d").join: "\n"; |
@coprime-triplets[0..(@coprime-triplets.first: * == 42, :k)].batch(10)».fmt("%4d").join: "\n"; |
||
put "\nAnd for the heck of it: |
put "\nAnd for the heck of it: 1001st through 1050th Coprime triplet:\n", |
||
@coprime-triplets[1000..1049].batch(10)».fmt("%4d").join: "\n";</ |
@coprime-triplets[1000..1049].batch(10)».fmt("%4d").join: "\n";</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Coprime triplets before first > 50: |
<pre>Coprime triplets before first > 50: |
||
Line 177: | Line 975: | ||
121 48 125 127 42 |
121 48 125 127 42 |
||
And for the heck of it: |
And for the heck of it: 1001st through 1050th Coprime triplet: |
||
682 1293 1361 680 1287 1363 686 1299 1367 688 |
682 1293 1361 680 1287 1363 686 1299 1367 688 |
||
1305 1369 692 1311 1373 694 1317 1375 698 1323 |
1305 1369 692 1311 1373 694 1317 1375 698 1323 |
||
Line 185: | Line 983: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight 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*/ |
parse arg n cols . /*obtain optional arguments from the CL*/ |
||
if n=='' | n=="," then n= 50 /*Not specified? Then use the default.*/ |
if n=='' | n=="," then n= 50 /*Not specified? Then use the default.*/ |
||
Line 218: | Line 1,016: | ||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? |
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</ |
gcd: procedure; parse arg x,y; do until _==0; _= x//y; x= y; y= _; end; return x</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 233: | Line 1,031: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
see "working..." + nl |
see "working..." + nl |
||
row = 2 |
row = 2 |
||
Line 282: | Line 1,080: | ||
see nl + "Found " + row + " coprime triplets" + nl |
see nl + "Found " + row + " coprime triplets" + nl |
||
see "done..." + nl |
see "done..." + nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 293: | Line 1,091: | ||
Found 36 coprime triplets |
Found 36 coprime triplets |
||
done... |
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}}== |
|||
<syntaxhighlight lang="ruby">list = [1, 2] |
|||
available = (1..50).to_a - list |
|||
loop do |
|||
i = available.index{|a| list.last(2).all?{|b| a.gcd(b) == 1}} |
|||
break if i.nil? |
|||
list << available.delete_at(i) |
|||
end |
|||
puts list.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|Sidef}}== |
|||
<syntaxhighlight lang="ruby">func coprime_triplets(callback) { |
|||
var ( |
|||
list = [1,2], |
|||
a = 1, |
|||
b = 2, |
|||
k = 3, |
|||
seen = Set() |
|||
) |
|||
loop { |
|||
for (var n = k; true; ++n) { |
|||
if (!seen.has(n) && is_coprime(n, a) && is_coprime(n, b)) { |
|||
list << n |
|||
seen << n |
|||
callback(list) && return list |
|||
(a, b) = (b, n) |
|||
while (seen.has(k)) { |
|||
seen.remove(k++) |
|||
} |
|||
break |
|||
} |
|||
} |
|||
} |
|||
} |
|||
say "Coprime triplets before first term is > 50:" |
|||
coprime_triplets({|list| |
|||
list.tail >= 50 |
|||
}).first(-1).slices(10).each { .«%« '%4d' -> join(' ').say } |
|||
say "\nLeast Coprime triplets that encompass 1 through 50:" |
|||
coprime_triplets({|list| |
|||
list.sort.first(50) == @(1..50) |
|||
}).slices(10).each { .«%« '%4d' -> join(' ').say } |
|||
say "\n1001st through 1050th Coprime triplet:" |
|||
coprime_triplets({|list| |
|||
list.len == 1050 |
|||
}).last(50).slices(10).each { .«%« '%4d' -> join(' ').say }</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Coprime triplets before first term is > 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 |
|||
Least 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 |
|||
1001st 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 |
|||
</pre> |
</pre> |
||
Line 298: | Line 1,205: | ||
{{trans|Phix}} |
{{trans|Phix}} |
||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
{{libheader|Wren-seq}} |
|||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="wren">import "./math" for Int |
||
import "/ |
import "./fmt" for Fmt |
||
import "/fmt" for Fmt |
|||
var limit = 50 |
var limit = 50 |
||
Line 316: | Line 1,221: | ||
} |
} |
||
System.print("Coprime triplets under %(limit):") |
System.print("Coprime triplets under %(limit):") |
||
Fmt.tprint("$2d", cpt, 10) |
|||
System.print("\nFound %(cpt.count) such numbers.")</ |
System.print("\nFound %(cpt.count) such numbers.")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 328: | Line 1,233: | ||
Found 36 such numbers. |
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> |
</pre> |
Latest revision as of 11:04, 21 November 2023
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
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 yet in the sequence.
p and q are coprimes if they have no common factors other than 1.
Let p, q < 50
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(‘ ’))
- Output:
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
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
- Output:
Screenshot from Atari 8-bit computer
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
ALGOL 68
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 #
# iterative Greatest Common Divisor routine, returns the gcd of m and n #
PROC gcd = ( INT m, n )INT:
BEGIN
INT a := ABS m, b := ABS n;
WHILE b /= 0 DO
INT new a = b;
b := a MOD b;
a := new a
OD;
a
END # gcd # ;
# returns an array of the coprime triplets up to n #
OP COPRIMETRIPLETS = ( INT n )[]INT:
BEGIN
[ 1 : n ]INT result;
IF n > 0 THEN
result[ 1 ] := 1;
IF n > 1 THEN
[ 1 : n ]BOOL used;
used[ 1 ] := used[ 2 ] := TRUE;
FOR i FROM 3 TO n DO used[ i ] := FALSE; result[ i ] := 0 OD;
result[ 2 ] := 2;
FOR i FROM 3 TO n DO
INT p1 = result[ i - 1 ];
INT p2 = result[ i - 2 ];
BOOL found := FALSE;
FOR j TO n WHILE NOT found DO
IF NOT used[ j ] THEN
found := gcd( p1, j ) = 1 AND gcd( p2, j ) = 1;
IF found THEN
used[ j ] := TRUE;
result[ i ] := j
FI
FI
OD
OD
FI
FI;
result
END # COPRIMETRIPLETS # ;
[]INT cps = COPRIMETRIPLETS 49;
INT printed := 0;
FOR i TO UPB cps DO
IF cps[ i ] /= 0 THEN
print( ( whole( cps[ i ], -3 ) ) );
printed +:= 1;
IF printed MOD 10 = 0 THEN print( ( newline ) ) FI
FI
OD;
print( ( newline, "Found ", whole( printed, 0 ), " coprime triplets up to ", whole( UPB cps, 0 ), newline ) )
END
- Output:
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 up to 49
ALGOL W
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 %
integer procedure gcd ( integer value m, n ) ;
begin
integer a, b;
a := abs m;
b := abs n;
while b not = 0 do begin
integer newA;
newA := b;
b := a rem b;
a := newA
end while_b_ne_0 ;
a
end gcd ;
% construct the sequence %
integer array seq ( 1 :: 49 );
integer sCount;
seq( 1 ) := 1; seq( 2 ) := 2; for i := 3 until 49 do seq( i ) := 0;
for i := 3 until 49 do begin
integer s1, s2, lowest;
s1 := seq( i - 1 );
s2 := seq( i - 2 );
lowest := 2;
while begin logical candidate;
lowest := lowest + 1;
candidate := gcd( s1, lowest ) = 1 and gcd( s2, lowest ) = 1;
if candidate then begin
% lowest is coprime to the previous two elements %
% check it hasn't appeared already %
for pos := 1 until i - 1 do begin
candidate := candidate and lowest not = seq( pos );
end for_pos ;
if candidate then seq( i ) := lowest;
end if_lowest_coprime_to_s1_and_s2 ;
not candidate and lowest < 50
end do begin end while_not_found
end for_i ;
% show the sequence %
sCount := 0;
for i := 1 until 49 do begin
if seq( i ) not = 0 then begin
writeon( i_w := 2, s_w := 0, " ", seq( i ) );
sCount := sCount + 1;
if sCount rem 10 = 0 then write()
end if_seq_i_ne_0
end for_i ;
write( i_w := 1, s_w := 0, sCount, " coprime triplets below 50" )
end.
- Output:
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 36 coprime triplets below 50
AppleScript
on hcf(a, b)
repeat until (b = 0)
set x to a
set a to b
set b to x mod b
end repeat
if (a < 0) then return -a
return a
end hcf
on coprimeTriplets(max)
if (max < 3) then return {}
script o
property candidates : {}
property output : {1, 2}
end script
-- When repeatedly searching for lowest unused numbers, it's faster in
-- AppleScript to take numbers from a preset list of candidates which
-- grows shorter from at or near the low end as used numbers are removed
-- than it is to test increasing numbers of previous numbers each time
-- against a list that's growing longer with them.
-- Generate the list of candidates here.
repeat with i from 3 to max
set end of o's candidates to i
end repeat
set candidateCount to max - 2
set {p1, p2} to o's output
set ok to true
repeat while (ok) -- While suitable coprimes found and candidates left.
repeat with i from 1 to candidateCount
set q to item i of o's candidates
set ok to ((hcf(p1, q) is 1) and (hcf(p2, q) is 1))
if (ok) then -- q is coprime with both p1 and p2.
set end of o's output to q
set p1 to p2
set p2 to q
-- Remove q from the candidate list.
set item i of o's candidates to missing value
set o's candidates to o's candidates's numbers
set candidateCount to candidateCount - 1
set ok to (candidateCount > 0)
exit repeat
end if
end repeat
end repeat
return o's output
end coprimeTriplets
-- Task code:
return coprimeTriplets(49)
- Output:
{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}
Arturo
lst: [1 2]
while [true][
n: 3
prev2: lst\[dec dec size lst]
prev1: last lst
while -> any? @[
contains? lst n
1 <> gcd @[n prev2]
1 <> gcd @[n prev1]
] -> n: n + 1
if n >= 50 -> break
'lst ++ n
]
loop split.every:10 lst 'a ->
print map a => [pad to :string & 3]
- Output:
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
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;
}
- Output:
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
Delphi
program Coprime_triplets;
{$APPTYPE CONSOLE}
uses
System.SysUtils;
//https://rosettacode.org/wiki/Greatest_common_divisor#Pascal_.2F_Delphi_.2F_Free_Pascal
function Gcd(u, v: longint): longint;
begin
if v = 0 then
EXIT(u);
result := Gcd(v, u mod v);
end;
function IsIn(value: Integer; a: TArray<Integer>): boolean;
begin
for var e in a do
if e = value then
exit(true);
Result := false;
end;
function CoprimeTriplets(less_than: Integer = 50): TArray<Integer>;
var
cpt: TArray<Integer>;
_end: Integer;
begin
cpt := [1, 2];
_end := high(cpt);
while True do
begin
var m := 1;
while IsIn(m, cpt) or (gcd(m, cpt[_end]) <> 1) or (gcd(m, cpt[_end - 1]) <> 1) do
inc(m);
if m >= less_than then
exit(cpt);
SetLength(cpt, Length(cpt) + 1);
_end := high(cpt);
cpt[_end] := m;
end;
end;
begin
var trps := CoprimeTriplets();
writeln('Found ', length(trps), ' coprime triplets less than 50:');
for var i := 0 to High(trps) do
begin
write(trps[i]: 2, ' ');
if (i + 1) mod 10 = 0 then
writeln;
end;
{$IFNDEF UNIX} Readln; {$ENDIF}
end.
F#
// Coprime triplets: Nigel Galloway. May 12th., 2021
let rec fN g=function 0->g=1 |n->fN n (g%n)
let rec fG t n1 n2=seq{let n=seq{1..0x0FFFFFFF}|>Seq.find(fun n->not(List.contains n t) && fN n1 n && fN n2 n) in yield n; yield! cT(n::t) n2 n}
let cT=seq{yield 1; yield 2; yield! fG [1;2] 1 2}
cT|>Seq.takeWhile((>)50)|>Seq.iter(printf "%d "); printfn ""
- Output:
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
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
- 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
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
- 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
Go
package main
import (
"fmt"
"rcu"
)
func contains(a []int, v int) bool {
for _, e := range a {
if e == v {
return true
}
}
return false
}
func main() {
const limit = 50
cpt := []int{1, 2}
for {
m := 1
l := len(cpt)
for contains(cpt, m) || rcu.Gcd(m, cpt[l-1]) != 1 || rcu.Gcd(m, cpt[l-2]) != 1 {
m++
}
if m >= limit {
break
}
cpt = append(cpt, m)
}
fmt.Printf("Coprime triplets under %d:\n", limit)
for i, t := range cpt {
fmt.Printf("%2d ", t)
if (i+1)%10 == 0 {
fmt.Println()
}
}
fmt.Printf("\n\nFound %d such numbers\n", len(cpt))
}
- 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
Haskell
import Data.List (find, transpose, unfoldr)
import Data.List.Split (chunksOf)
import qualified Data.Set as S
--------------------- COPRIME TRIPLES --------------------
coprimeTriples :: Integral a => [a]
coprimeTriples =
[1, 2] <> unfoldr go (S.fromList [1, 2], (1, 2))
where
go (seen, (a, b)) =
Just
(c, (S.insert c seen, (b, c)))
where
Just c =
find
( ((&&) . flip S.notMember seen)
<*> ((&&) . coprime a <*> coprime b)
)
[3 ..]
coprime :: Integral a => a -> a -> Bool
coprime a b = 1 == gcd a b
--------------------------- TEST -------------------------
main :: IO ()
main =
let xs = takeWhile (< 50) coprimeTriples
in putStrLn (show (length xs) <> " terms below 50:\n")
>> putStrLn
( spacedTable
justifyRight
(chunksOf 10 (show <$> xs))
)
-------------------------- FORMAT ------------------------
spacedTable ::
(Int -> Char -> String -> String) -> [[String]] -> String
spacedTable aligned rows =
unlines $
unwords
. zipWith
(`aligned` ' ')
(maximum . fmap length <$> transpose rows)
<$> rows
justifyRight :: Int -> Char -> String -> String
justifyRight n c = (drop . length) <*> (replicate n c <>)
- Output:
36 terms below 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
jq
Works with gojq, the Go implementation of jq
Preliminaries
# jq optimizes the recursive call of _gcd in the following:
def gcd(a;b):
def _gcd:
if .[1] != 0 then [.[1], .[0] % .[1]] | _gcd else .[0] end;
[a,b] | _gcd ;
# Pretty-printing
def nwise($n):
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;
n;
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
The task
# Input: an upper bound greater than 2
# Output: the array of coprime triplets [1,2 ... n] where n is less than the upper bound
def coprime_triplets:
. as $less_than
| {cpt: [1, 2], m:0}
| until( .m >= $less_than;
.m = 1
| .cpt as $cpt
| until( (.m | IN($cpt[]) | not) and (gcd(.m; $cpt[-1]) == 1) and (gcd(.m; $cpt[-2]) == 1);
.m += 1 )
| .cpt = $cpt + [.m] )
| .cpt[:-1];
50 | coprime_triplets
| (nwise(10) | map(lpad(2)) | join(" "))
- Output:
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
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))
- 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
Mathematica/Wolfram Language
ClearAll[NextTerm]
NextTerm[a_List] := Module[{pred1, pred2, cands},
{pred1, pred2} = Take[a, -2];
cands =
Select[Range[50], CoprimeQ[#, pred1] && CoprimeQ[#, pred2] &];
cands = Complement[cands, a];
If[Length[cands] > 0,
Append[a, First[cands]]
,
a
]
]
Nest[NextTerm, {1, 2}, 120]
- Output:
{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}
Nim
import math, strutils
var list = @[1, 2]
while true:
var n = 3
let prev2 = list[^2]
let prev1 = list[^1]
while n in list or gcd(n, prev2) != 1 or gcd(n, prev1) != 1:
inc n
if n >= 50: break
list.add n
echo list.join(" ")
- Output:
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
Perl
use strict;
use warnings;
use feature <state say>;
use ntheory 'gcd';
use List::Util 'first';
use List::Lazy 'lazy_list';
use enum qw(False True);
use constant Inf => 1e5;
my $ct = lazy_list {
state @c = (1, 2);
state %seen = (1 => True, 2 => True);
state $min = 3;
my $g = $c[-2] * $c[-1];
my $n = first { !$seen{$_} and gcd($_,$g) == 1 } $min .. Inf;
$seen{$n} = True;
$min = first { !$seen{$_} } $min .. Inf;
push @c, $n;
shift @c
};
my @ct;
do { push @ct, $ct->next() } until $ct[-1] > 50; pop @ct;
say join ' ', @ct
- Output:
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
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")
- Output:
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
Quackery
coprime
is defined at Coprimes#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
- Output:
[ 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
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: 1001st through 1050th Coprime triplet:\n",
@coprime-triplets[1000..1049].batch(10)».fmt("%4d").join: "\n";
- 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: 1001st 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
/*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
- 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
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
- 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...
RPL
≪ {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
≫ ≫ ‘TASK’ STO
- Output:
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}
Ruby
list = [1, 2]
available = (1..50).to_a - list
loop do
i = available.index{|a| list.last(2).all?{|b| a.gcd(b) == 1}}
break if i.nil?
list << available.delete_at(i)
end
puts list.join(" ")
- Output:
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
Sidef
func coprime_triplets(callback) {
var (
list = [1,2],
a = 1,
b = 2,
k = 3,
seen = Set()
)
loop {
for (var n = k; true; ++n) {
if (!seen.has(n) && is_coprime(n, a) && is_coprime(n, b)) {
list << n
seen << n
callback(list) && return list
(a, b) = (b, n)
while (seen.has(k)) {
seen.remove(k++)
}
break
}
}
}
}
say "Coprime triplets before first term is > 50:"
coprime_triplets({|list|
list.tail >= 50
}).first(-1).slices(10).each { .«%« '%4d' -> join(' ').say }
say "\nLeast Coprime triplets that encompass 1 through 50:"
coprime_triplets({|list|
list.sort.first(50) == @(1..50)
}).slices(10).each { .«%« '%4d' -> join(' ').say }
say "\n1001st through 1050th Coprime triplet:"
coprime_triplets({|list|
list.len == 1050
}).last(50).slices(10).each { .«%« '%4d' -> join(' ').say }
- Output:
Coprime triplets before first term is > 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 Least 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 1001st 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
Wren
import "./math" for Int
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):")
Fmt.tprint("$2d", cpt, 10)
System.print("\nFound %(cpt.count) such numbers.")
- 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.
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;
];
]
- Output:
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