Stern-Brocot sequence: Difference between revisions
m
→{{header|Wren}}: Minor tidy
Not a robot (talk | contribs) (Add Modula-2) |
m (→{{header|Wren}}: Minor tidy) |
||
(19 intermediate revisions by 12 users not shown) | |||
Line 11:
#* 1, 1, 2, 1
# Consider the next member of the series, (the third member i.e. 2)
# GOTO 3
#*
#* ─── Expanding another loop we get: ───
#*
Line 25:
* Create a function/method/subroutine/procedure/... to generate the Stern-Brocot sequence of integers using the method outlined above.
* Show the first fifteen members of the sequence. (This should be: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4)
* Show the (1-based) index of where the numbers 1-to-10
* Show the (1-based) index of where the number 100 first appears in the sequence.
* Check that the greatest common divisor of all the two consecutive members of the series up to the 1000<sup>th</sup> member, is always one.
Line 39:
;Ref:
* [https://www.youtube.com/watch?v=DpwUVExX27E Infinite Fractions - Numberphile] (Video).
* [http://www.ams.org/samplings/feature-column/fcarc-stern-brocot Trees, Teeth, and Time: The mathematics of clock making].
* [https://oeis.org/A002487 A002487] The On-Line Encyclopedia of Integer Sequences.
<br><br>
Line 46:
{{trans|Python}}
<
V sb = [1, 1]
V i = 0
Line 65:
V n_gcd = 1000
V s = stern_brocot(series -> series.len < :n_gcd)[0 .< n_gcd]
assert(all(zip(s, s[1..]).map((prev, this) -> gcd(prev, this) == 1)), ‘A fraction from adjacent terms is reducible’)</
{{out}}
Line 87:
=={{header|360 Assembly}}==
{{trans|Fortran}}
<
STERNBR CSECT
USING STERNBR,R13 base register
Line 158:
SB DC (NN)H'1' sb(nn)
REGEQU
END STERNBR</
{{out}}
<pre>
Line 176:
</pre>
The nice part is the coding of the sequense:
<
while(k<nn);
k++; sb[k]=sb[k-i]+sb[k-j];
k++; sb[k]=sb[k-j];
i++; j++;
} </
Only five registers are used. No Horner's rule to access sequence items.
<
LA R2,SB+2 i=1; @sb(k-i)
LA R3,SB+0 j=2; @sb(k-j)
Line 196:
STH R0,0(R4) sb(k)=sb(k-j)
LA R2,2(R2) @sb(k-i)++
BCT R1,LOOP k--; if k>0 then goto loop </
=={{header|8080 Assembly}}==
<syntaxhighlight lang="8080asm">puts: equ 9 ; CP/M syscall to print a string
org 100h
;;; Generate the first 1200 elements of the Stern-Brocot sequence
Line 335 ⟶ 334:
gcdn: db 'GCD not 1 at: $'
gcdy: db 'GCD of all pairs of consecutive members is 1.$'
seq: db 1,1 ; Sequence stored here</
{{out}}
Line 345 ⟶ 344:
=={{header|8086 Assembly}}==
<syntaxhighlight lang="asm">puts: equ 9
cpu 8086
bits 16
Line 446 ⟶ 444:
numbuf: db ' $'
nl: db 13,10,'$'
seq: db 1,1</
{{out}}
Line 455 ⟶ 453:
GCD of all pairs of consecutive members is 1.</pre>
=={{header|Action!}}==
<syntaxhighlight lang="action!">PROC Generate(BYTE ARRAY seq INT POINTER count INT minCount,maxVal)
INT i
seq(0)=1 seq(1)=1 count^=2 i=1
WHILE count^<minCount OR seq(count^-1)#maxVal AND seq(count^-2)#maxVal
DO
seq(count^)=seq(i-1)+seq(i)
seq(count^+1)=seq(i)
count^==+2 i==+1
OD
RETURN
PROC PrintSeq(BYTE ARRAY seq INT count)
INT i
PrintF("First %I items:%E",count)
FOR i=0 TO count-1
DO
PrintB(seq(i)) Put(32)
OD
PutE() PutE()
RETURN
PROC PrintLoc(BYTE ARRAY seq INT seqCount
BYTE ARRAY loc INT locCount)
INT i,j
BYTE value
FOR i=0 TO locCount-1
DO
j=0 value=loc(i)
WHILE seq(j)#value
DO
j==+1
OD
PrintF("%B appears at position %I%E",value,j+1)
OD
PutE()
RETURN
BYTE FUNC Gcd(BYTE a,b)
BYTE 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)
PROC PrintGcd(BYTE ARRAY seq INT count)
INT i
FOR i=0 TO count-2
DO
IF Gcd(seq(i),seq(i+1))>1 THEN
PrintF("GCD between %I and %I item is greater than 1",i+1,i+2)
RETURN
FI
OD
Print("GCD between all two consecutive items of the sequence is equal 1")
RETURN
PROC Main()
BYTE ARRAY seq(2000),loc=[1 2 3 4 5 6 7 8 9 10 100]
INT count
Generate(seq,@count,1000,100)
PrintSeq(seq,15)
PrintLoc(seq,count,loc,11)
PrintGcd(seq,1000)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Stern-Brocot_sequence.png Screenshot from Atari 8-bit computer]
<pre>
First 15 items:
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
1 appears at position 1
2 appears at position 3
3 appears at position 5
4 appears at position 9
5 appears at position 11
6 appears at position 33
7 appears at position 19
8 appears at position 21
9 appears at position 35
10 appears at position 39
100 appears at position 1179
GCD between all two consecutive items of the sequence is equal 1
</pre>
=={{header|Ada}}==
<syntaxhighlight lang="ada">with Ada.Text_IO, Ada.Containers.Vectors;
procedure Sequence is
Line 552 ⟶ 645:
when Constraint_Error => Put_Line("Some GCD > 1; this is wrong!!!") ;
end;
end Sequence;</
{{out}}
Line 563 ⟶ 656:
=={{header|ALGOL 68}}==
<
# subsequent members are the previous two members summed followed by #
# the previous #
Line 636 ⟶ 729:
OD;
print( ( "Element pairs up to 1000 are ", IF all coprime THEN "" ELSE "NOT " FI, "coprime", newline ) )
END</
{{out}}
<pre>
Line 650 ⟶ 743:
=={{header|ALGOL-M}}==
<
integer array S[1:1200];
integer i,ok;
Line 698 ⟶ 791:
end;
if ok = 1 then write("The GCD of each pair of consecutive members is 1.");
end</
{{out}}
<pre>First 15 numbers:
Line 719 ⟶ 812:
The GCD of each pair of consecutive members is 1.</pre>
=={{header|
Version: hopper-FLOW!:
<syntaxhighlight lang="amazing hopper">
#include <flow.h>
#include <flow-flow.h>
DEF-MAIN(argv,argc)
CLR-SCR
SET( amount, 1200 )
DIM(amount) AS-ONES( Stern )
/* Generate Stern-Brocot sequence: */
GOSUB( Generate Sequence )
PRNL( "Find 15 first: ", [1:19] CGET(Stern) )
/* show Stern-Brocot sequence: */
SET( i, 1 ), ITERATE( ++i, LE?(i,10), \
PRN( "First ",i," at "), {i} GOSUB( Find First ), PRNL )
PRN( "First 100 at "), {100} GOSUB( Find First ), PRNL
/* check GCD: */
ODD-POS, CGET(Stern), EVEN-POS, CGET(Stern), COMP-GCD, GET-SUMMATORY, DIV-INTO( DIV(amount,2) )
IF ( IS-EQ?(1), PRNL("The GCD of every pair of adjacent elements is 1"),\
PRNL("Stern-Brocot Sequence is wrong!") )
END
RUTINES
DEF-FUN(Find First, n )
RET ( SCAN(1, n, Stern) )
DEF-FUN(Generate Sequence)
SET(i,2)
FOR( LE?(i, DIV(amount,2)), ++i )
[i] GET( Stern ), [ MINUS-ONE(i) ] GET( Stern ), ADD-IT
[ SUB(MUL(i,2),1) ] CPUT( Stern )
[i] GET( Stern ), [MUL(i,2)] CPUT( Stern )
NEXT
RET
</syntaxhighlight>
{{out}}
<pre>
Find 15 first: 1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7
First 1 at 1
First 2 at 3
First 3 at 5
First 4 at 9
First 5 at 11
First 6 at 33
First 7 at 19
First 8 at 21
First 9 at 35
First 10 at 39
First 100 at 1179
The GCD of every pair of adjacent elements is 1
</pre>
=={{header|APL}}==
<syntaxhighlight lang="apl">task←{
stern←{⍵{
⍺←0 ⋄ ⍺⍺≤⍴⍵:⍺⍺↑⍵
Line 731 ⟶ 881:
⎕←'Location of 100:',seq⍳100
⎕←'All GCDs 1:','no' 'yes'[1+1∧.=2∨/1000↑seq]
}</
{{out}}
Line 741 ⟶ 891:
=={{header|AppleScript}}==
<
use framework "Foundation"
use scripting additions
Line 1,281 ⟶ 1,431:
return lst
end tell
end zipWith</
{{Out}}
<pre>[1,1,2,1,3,2,3,1,4,3,5,2,5,3,4]
Line 1,287 ⟶ 1,437:
[100,1179]
true</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">sternBrocot: function [mx][
seq: [1 1]
result: [[1 1] [2 1]]
idx: 1
while [idx < mx][
'seq ++ seq\[idx] + seq\[idx - 1]
'result ++ @[@[size seq, last seq]]
'seq ++ seq\[idx]
'result ++ @[@[size seq, last seq]]
inc 'idx
]
return result
]
sbs: sternBrocot 1000
print ["First 15 terms:" join.with:", " first.n:15 map sbs 'sb -> to :string last sb]
print ""
indexes: array.of:101 0
toFind: 101
loop sbs 'sb [
[i, n]: sb
if and? -> contains? 1..100 n -> zero? indexes\[n][
indexes\[n]: i
dec 'toFind
if zero? toFind [
break
]
]
]
loop (@1..10) ++ 100 'n ->
print ["Index of first occurrence of number" n ":" indexes\[n]]
print ""
prev: 1
idx: 1
loop sbs 'sb [
[i, n]: sb
if not? one? gcd @[prev n] -> break
prev: n
inc 'idx
if idx > 1000 -> break
]
print (idx =< 1000)? -> ["Found two successive terms at index:" idx]
-> "All consecutive terms up to the 1000th member have a GCD equal to one."</syntaxhighlight>
{{out}}
<pre>First 15 terms: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4
Index of first occurrence of number 1 : 1
Index of first occurrence of number 2 : 3
Index of first occurrence of number 3 : 5
Index of first occurrence of number 4 : 9
Index of first occurrence of number 5 : 11
Index of first occurrence of number 6 : 33
Index of first occurrence of number 7 : 19
Index of first occurrence of number 8 : 21
Index of first occurrence of number 9 : 35
Index of first occurrence of number 10 : 39
Index of first occurrence of number 100 : 1179
All consecutive terms up to the 1000th member have a GCD equal to one.</pre>
=={{header|AutoHotkey}}==
<
Loop, 10
FoundList .= "First " A_Index " found at " Found[A_Index] "`n"
Line 1,365 ⟶ 1,586:
b := Mod(a | 0x0, a := b)
return a
}</
{{out}}
<pre>First 15: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4
Line 1,382 ⟶ 1,603:
=={{header|BASIC}}==
<syntaxhighlight lang="basic">10 DEFINT A,B,I,J,S: DIM S(1200)
20 S(1)=1: S(2)=1
30 FOR I=2 TO 600
Line 1,404 ⟶ 1,624:
190 NEXT I
200 PRINT "All GCDs are 1."
210 END</
{{out}}
Line 1,422 ⟶ 1,642:
All GCDs are 1.
</pre>
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="basic256">arraybase 1
max = 2000
global stern
dim stern(max+2)
subroutine SternBrocot()
stern[1] = 1
stern[2] = 1
i = 2 : n = 2 : ub = stern[?]
while i < ub
i += 1
stern[i] = stern[n] + stern[n-1]
i += 1
stern[i] = stern[n]
n += 1
end while
end subroutine
function gcd(x, y)
while y
t = y
y = x mod y
x = t
end while
gcd = x
end function
call SternBrocot()
print "The first 15 are: ";
for i = 1 to 15
print stern[i]; " ";
next i
print : print
print "Index First nr."
d = 1
for i = 1 to max
if stern[i] = d then
print i; chr(9); stern[i]
d += 1
if d = 11 then d = 100
if d = 101 then exit for
i = 0
end if
next i
print : print
d = 0
for i = 1 to 1000
if gcd(stern[i], stern[i+1]) <> 1 then
d = gcd(stern[i], stern[i+1])
exit for
end if
next i
if d = 0 then
print "GCD of two consecutive members of the series up to the 1000th member is 1"
else
print "The GCD for index "; i; " and "; i+1; " = "; d
end if</syntaxhighlight>
{{out}}
<pre>Igual que la entrada de FreeBASIC.</pre>
==={{header|QBasic}}===
{{trans|FreeBASIC}}
{{works with|QBasic|1.1}}
<syntaxhighlight lang="qbasic">CONST max = 2000
DIM SHARED stern(max + 2)
FUNCTION gcd (x, y)
WHILE y
t = y
y = x MOD y
x = t
WEND
gcd = x
END FUNCTION
SUB SternBrocot
stern(1) = 1
stern(2) = 1
i = 2: n = 2: ub = UBOUND(stern)
DO WHILE i < ub
i = i + 1
stern(i) = stern(n) + stern(n - 1)
i = i + 1
stern(i) = stern(n)
n = n + 1
LOOP
END SUB
SternBrocot
PRINT "The first 15 are: ";
FOR i = 1 TO 15
PRINT stern(i); " ";
NEXT i
PRINT : PRINT
PRINT " Index First nr."
d = 1
FOR i = 1 TO max
IF stern(i) = d THEN
PRINT USING " ######"; i; stern(i)
d = d + 1
IF d = 11 THEN d = 100
IF d = 101 THEN EXIT FOR
i = 0
END IF
NEXT i
PRINT : PRINT
d = 0
FOR i = 1 TO 1000
IF gcd(stern(i), stern(i + 1)) <> 1 THEN
d = gcd(stern(i), stern(i + 1))
EXIT FOR
END IF
NEXT i
IF d <> 0 THEN
PRINT "GCD of two consecutive members of the series up to the 1000th member is 1"
ELSE
PRINT "The GCD for index "; i; " and "; i + 1; " = "; d
END IF</syntaxhighlight>
{{out}}
<pre>Igual que la entrada de FreeBASIC.</pre>
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="yabasic">limite = 2000
dim stern(limite+2)
sub SternBrocot()
stern(1) = 1
stern(2) = 1
i = 2 : n = 2 : ub = arraysize(stern(),1)
while i < ub
i = i + 1
stern(i) = stern(n) + stern(n -1)
i = i + 1
stern(i) = stern(n)
n = n + 1
wend
end sub
sub gcd(p, q)
if q = 0 return p
return gcd(q, mod(p, q))
end sub
SternBrocot()
print "The first 15 are: ";
for i = 1 to 15
print stern(i), " ";
next i
print "\n\n Index First nr."
d = 1
for i = 1 to limite
if stern(i) = d then
print i using "######", stern(i) using "######"
d = d + 1
if d = 11 d = 100
if d = 101 break
i = 0
end if
next i
print : print
d = 0
for i = 1 to 1000
if gcd(stern(i), stern(i+1)) <> 1 then
d = gcd(stern(i), stern(i+1))
break
end if
next i
if d = 0 then
print "GCD of two consecutive members of the series up to the 1000th member is 1"
else
print "The GCD for index ", i, " and ", i+1, " = ", d
end if</syntaxhighlight>
{{out}}
<pre>Igual que la entrada de FreeBASIC.</pre>
=={{header|BCPL}}==
<
manifest $( AMOUNT = 1200 $)
Line 1,467 ⟶ 1,883:
$) then
writes("*NThe GCD of each pair of consecutive members is 1.*N")
$)</
{{out}}
<pre>First 15 numbers: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
Line 1,485 ⟶ 1,901:
The GCD of each pair of consecutive members is 1.</pre>
=={{header|C}}==
Recursive function.
<
typedef unsigned int uint;
Line 1,524 ⟶ 1,941:
return 0;
}</
{{out}}
<pre>
Line 1,542 ⟶ 1,959:
</pre>
The above <code>f()</code> can be replaced by the following, which is much faster but probably less obvious as to how it arrives from the recurrence relations.
<
{
uint a = 1, b = 0;
Line 1,551 ⟶ 1,968:
}
return b;
}</
=={{header|C sharp|C#}}==
<
using System.Collections.Generic;
using System.Linq;
Line 1,579 ⟶ 1,996:
" series up to the {0}th item is {1}always one.", max, good ? "" : "not ");
}
}</
{{out}}
<pre>The first 15 items In the Stern-Brocot sequence: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4
Line 1,600 ⟶ 2,017:
=={{header|C++}}==
<
#include <iostream>
#include <iomanip>
Line 1,651 ⟶ 2,068:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,694 ⟶ 2,111:
=={{header|Clojure}}==
<
(defn sb-step [v]
(let [i (quot (count v) 2)]
Line 1,727 ⟶ 2,144:
true)
(report-sb)</
{{Output}}
Line 1,747 ⟶ 2,164:
===Clojure: Using Lazy Sequences===
<
(defn gcd
"(gcd a b) computes the greatest common divisor of a and b."
Line 1,779 ⟶ 2,196:
(println (every? (fn [[ith ith-plus-1]] (= (gcd ith ith-plus-1) 1))
one-thousand-pairs))
</syntaxhighlight>
{{Output}}
Line 1,797 ⟶ 2,214:
true
</pre>
=={{header|CLU}}==
<syntaxhighlight lang="clu">stern = proc (n: int) returns (array[int])
s: array[int] := array[int]$fill(1, n, 1)
for i: int in int$from_to(2, n/2) do
s[i*2-1] := s[i] + s[i-1]
s[i*2] := s[i]
end
return (s)
end stern
gcd = proc (a,b: int) returns (int)
while b ~= 0 do
a, b := b, a//b
end
return (a)
end gcd
find = proc [T: type] (a: array[T], val: T) returns (int) signals (not_found)
where T has equal: proctype (T,T) returns (bool)
for i: int in array[T]$indexes(a) do
if a[i] = val then return (i) end
end
signal not_found
end find
start_up = proc ()
po: stream := stream$primary_output()
s: array[int] := stern(1200)
stream$puts(po, "First 15 numbers:")
for i: int in int$from_to(1, 15) do
stream$puts(po, " " || int$unparse(s[i]))
end
stream$putl(po, "")
for i: int in int$from_to(1, 10) do
stream$putl(po, "First " || int$unparse(i) || " at " ||
int$unparse(find[int](s, i)))
end
stream$putl(po, "First 100 at " || int$unparse(find[int](s, 100)))
begin
for i: int in int$from_to(2, array[int]$high(s)) do
if gcd(s[i-1], s[i]) ~= 1 then
exit gcd_not_one(i)
end
end
stream$putl(po, "The GCD of every pair of adjacent elements is 1.")
end except when gcd_not_one(i: int):
stream$putl(po, "The GCD of the pair at " || int$unparse(i) || " is not 1.")
end
end start_up</syntaxhighlight>
{{out}}
<pre>First 15 numbers: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
First 1 at 1
First 2 at 3
First 3 at 5
First 4 at 9
First 5 at 11
First 6 at 33
First 7 at 19
First 8 at 21
First 9 at 35
First 10 at 39
First 100 at 1179
The GCD of every pair of adjacent elements is 1.</pre>
=={{header|Common Lisp}}==
<
(declare ((or null (vector integer)) numbers))
(cond ((null numbers)
Line 1,854 ⟶ 2,338:
(first-1-to-10)
(first-100)
(check-gcd))</
{{out}}
<pre>First 15: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
Line 1,871 ⟶ 2,355:
=={{header|Cowgol}}==
<
# Redefining these is enough to change the type and length everywhere,
Line 1,947 ⟶ 2,431:
end loop;
print("All GCDs are 1.\n");</
{{out}}
Line 1,957 ⟶ 2,441:
=={{header|D}}==
{{trans|Python}}
<
/// Generates members of the stern-brocot series, in order,
Line 1,985 ⟶ 2,469:
assert(zip(s, s.dropOne).all!(ss => ss[].gcd == 1),
"A fraction from adjacent terms is reducible.");
}</
{{out}}
<pre>The first 15 values:
Line 2,003 ⟶ 2,487:
This uses a queue from the Queue/usage Task:
<
struct SternBrocot {
Line 2,020 ⟶ 2,504:
void main() {
SternBrocot().drop(50_000_000).front.writeln;
}</
{{out}}
<pre>7004</pre>
Line 2,026 ⟶ 2,510:
<b>Direct Version:</b>
{{trans|C}}
<
import std.stdio, std.numeric, std.range, std.algorithm, std.bigint, std.conv;
Line 2,053 ⟶ 2,537:
sternBrocot(10.BigInt ^^ 20_000).text.length.writeln;
}</
{{out}}
<pre>The first 15 values:
Line 2,070 ⟶ 2,554:
1-based index of the first occurrence of 100 in the series: 1179
7984</pre>
=={{header|EasyLang}}==
{{trans|Lua}}
<syntaxhighlight>
global sb[] .
proc sternbrocot n . .
sb[] = [ 1 1 ]
pos = 2
repeat
c = sb[pos]
sb[] &= c + sb[pos - 1]
sb[] &= c
pos += 1
until len sb[] >= n
.
.
func first v .
for i to len sb[]
if v <> 0
if sb[i] = v
return i
.
else
if sb[i] <> 0
return i
.
.
.
return 0
.
func gcd x y .
if y = 0
return x
.
return gcd y (x mod y)
.
func$ task5 .
for i to 1000
if gcd sb[i] sb[i + 1] <> 1
return "FAIL"
.
.
return "PASS"
.
sternbrocot 10000
write "Task 2: "
for i to 15
write sb[i] & " "
.
print "\n\nTask 3:"
for i to 10
print "\t" & i & " " & first i
.
print "\nTask 4: " & first 100
print "\nTask 5: " & task5
</syntaxhighlight>
{{out}}
<pre>
Task 2: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
Task 3:
1 1
2 3
3 5
4 9
5 11
6 33
7 19
8 21
9 35
10 39
Task 4: 1179
Task 5: PASS
</pre>
=={{header|EchoLisp}}==
=== Function ===
<
;; stern (2n ) = stern (n)
;; stern(2n+1) = stern(n) + stern(n+1)
Line 2,083 ⟶ 2,645:
(else (let ((m (/ (1- n) 2))) (+ (stern m) (stern (1+ m)))))))
(remember 'stern)
</syntaxhighlight>
{{out}}
<
; generate the sequence and check GCD
(for ((n 10000))
Line 2,106 ⟶ 2,668:
(stern 900000) → 446
(stern 900001) → 2479
</syntaxhighlight>
=== Stream ===
From [https://oeis.org/A002487 A002487], if we group the elements by two, we get (uniquely) all the rationals. Another way to generate the rationals, hence the stern sequence, is to iterate the function f(x) = floor(x) + 1 - fract(x).
<
;; grouping
(for ((i (in-range 2 40 2))) (write (/ (stern i)(stern (1+ i)))))
Line 2,125 ⟶ 2,687:
→ 1/2 1/3 2/3 1/4 3/5 2/5 3/4 1/5 4/7 3/8 5/7 2/7 5/8 3/7 4/5 1/6 5/9 4/11 7/10
</syntaxhighlight>
=={{header|Elixir}}==
<
def sequence do
Stream.unfold({0,{1,1}}, fn {i,acc} ->
Line 2,155 ⟶ 2,717:
end
SternBrocot.task</
{{out}}
Line 2,177 ⟶ 2,739:
=={{header|F_Sharp|F#}}==
===The function===
<
// Generate Stern-Brocot Sequence. Nigel Galloway: October 11th., 2018
let sb=Seq.unfold(fun (n::g::t)->Some(n,[g]@t@[n+g;g]))[1;1]
</syntaxhighlight>
===The Task===
Uses [[Greatest_common_divisor#F.23]]
<
sb |> Seq.take 15 |> Seq.iter(printf "%d ");printfn ""
[1..10] |> List.map(fun n->(n,(sb|>Seq.findIndex(fun g->g=n))+1)) |> List.iter(printf "%A ");printfn ""
printfn "%d" ((sb|>Seq.findIndex(fun g->g=100))+1)
printfn "There are %d consecutive members, of the first thousand members, with GCD <> 1" (sb |> Seq.take 1000 |>Seq.pairwise |> Seq.filter(fun(n,g)->gcd n g <> 1) |> Seq.length)
</syntaxhighlight>
{{out}}
<pre>
Line 2,199 ⟶ 2,761:
=={{header|Factor}}==
Using the alternative function given in the C example for computing the Stern-Brocot sequence.
<
math.ranges prettyprint sequences ;
IN: rosetta-code.stern-brocot
Line 2,229 ⟶ 2,791:
: main ( -- ) first15 first-appearances gcd-test ;
MAIN: main</
{{out}}
<pre>
Line 2,248 ⟶ 2,810:
=={{header|Forth}}==
<syntaxhighlight lang="forth">: stern ( n -- x : return N'th item of Stern-Brocot sequence)
dup 2 >= if
2 /mod swap if
Line 2,301 ⟶ 2,862:
task
bye</
{{out}}
Line 2,323 ⟶ 2,884:
{{trans|VBScript}}
===Fortran IV===
<
DIMENSION ISB(2400)
NN=2400
Line 2,353 ⟶ 2,914:
103 FORMAT(1X,'FIRST',I4,' AT ',I4)
5 CONTINUE
END </
{{out}}
<pre>
Line 2,372 ⟶ 2,933:
</pre>
===Fortran 90===
<
parameter (nn=2400)
dimension isb(nn)
Line 2,393 ⟶ 2,954:
write(*,"(1x,'First',i4,' at ',i4)") jj,i
end do
end </
{{out}}
<pre>
Line 2,412 ⟶ 2,973:
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 2,493 ⟶ 3,054:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>The first 15 are: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
Line 2,513 ⟶ 3,074:
=={{header|Go}}==
<
import (
Line 2,560 ⟶ 3,121:
}
return x
}</
<
//
// Generator() satisfies RC Task 1. For remaining tasks, Generator could be
Line 2,634 ⟶ 3,195:
}
}
}</
{{out}}
<pre>
Line 2,676 ⟶ 3,237:
=={{header|Haskell}}==
<
sb :: [Int]
Line 2,692 ⟶ 3,253:
print $
all (\(a, b) -> 1 == gcd a b) $
take 1000 $ zip sb (tail sb)</
{{out}}
<pre>[1,1,2,1,3,2,3,1,4,3,5,2,5,3,4]
Line 2,700 ⟶ 3,261:
Or, expressed in terms of iterate:
<
import Data.List (nubBy, sortOn)
import Data.Ord (comparing)
Line 2,727 ⟶ 3,288:
print $
(all ((1 ==) . uncurry gcd) . (zip <*> tail)) $
take 1000 sternBrocot</
{{Out}}
<pre>[1,1,2,1,3,2,3,1,4,3,5,2,5,3,4]
Line 2,735 ⟶ 3,296:
=={{header|J}}==
We have two different kinds of list specifications here (length of the sequence, and the presence of certain values in the sequence). Also the underlying list generation mechanism is somewhat arbitrary. So let's generate the sequence iteratively and provide a truth valued function of the intermediate sequences to determine when we have generated one which is adequately long:
<
ind=. 0
seq=. 1 1
Line 2,745 ⟶ 3,305:
seq=. seq, +/\. seq {~ _1 0 +ind
end.
)</
(Grammatical aside: this is an adverb which generates a noun without taking any x/y arguments. So usage is: <code>u sternbrocot</code>. J does have precedence rules, just not very many of them. Users of other languages can get a rough idea of the grammatical terms like this: adverb is approximately like a macro, verb approximately like a function and noun is approximately like a number. Also x and y are J's names for left and right noun arguments, and u and v are J's names for left and right verb arguments. An adverb has a left verb argument. There are some other important constraints but that's probably more than enough detail for this task.)
Line 2,751 ⟶ 3,311:
First fifteen members of the sequence:
<
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4</
One based indices of where numbers 1-10 first appear in the sequence:
<
1 3 5 9 11 33 19 21 35 39</
One based index of where the number 100 first appears:
<
1179</
List of distinct greatest common divisors of adjacent number pairs from a sternbrocot sequence which includes the first 1000 elements:
<
1</
=={{header|Java}}==
{{works with|Java|1.5+}}
This example generates the first 1200 members of the sequence since that is enough to cover all of the tests in the description. It borrows the <code>gcd</code> method from <code>BigInteger</code> rather than using its own.
<
import java.util.LinkedList;
Line 2,805 ⟶ 3,365:
System.out.println("All GCDs are" + (failure ? " not" : "") + " 1");
}
}</
{{out}}
<pre>The first 15 elements are: [1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]
Line 2,823 ⟶ 3,383:
=== Stern-Brocot Tree ===
{{works with|Java|8}}
<
import javax.swing.*;
Line 2,885 ⟶ 3,445:
});
}
}</
[[File:stern_brocot_tree_java.gif]]
=={{header|JavaScript}}==
<
'use strict';
Line 3,213 ⟶ 3,773:
// MAIN ---
return main();
})();</
{{Out}}
<pre>[1,1,2,1,3,2,3,1,4,3,5,2,5,3,4]
Line 3,225 ⟶ 3,785:
'''Foundations:'''
<
def _until:
if cond then . else (update | _until) end;
Line 3,236 ⟶ 3,796:
else [.[1], .[0] % .[1]] | rgcd
end;
[a,b] | rgcd ;</
'''The A002487 integer sequence:'''
Line 3,243 ⟶ 3,803:
The n-th element of the Rosetta Code sequence (counting from 1)
is thus a[n], which accords with the fact that jq arrays have an index origin of 0.
<
# generates an array with at least n elements of
# the A002487 sequence;
Line 3,260 ⟶ 3,820:
| if (.[$l-2] == -n) then .
else .[$l + 1] = .[$n] + .[$n+1]
end ) ;</
'''The tasks:'''
<
def stern_brocot(n): A002487(n+1) | .[1:n+1][];
Line 3,293 ⟶ 3,853:
"",
gcd_task
</syntaxhighlight>
{{out}}
<
First 15 integers of the Stern-Brocot sequence
as defined in the task description are:
Line 3,327 ⟶ 3,887:
index of 100 is 1179
GCDs are all 1</
=={{header|Julia}}==
{{trans|Python}}
<
function sternbrocot(f::Function=(x) -> length(x) ≥ 20)::Vector{Int}
Line 3,356 ⟶ 3,916:
else
println("Rejected.")
end</
{{out}}
Line 3,379 ⟶ 3,939:
=={{header|Kotlin}}==
<
val sbs = mutableListOf(1, 1)
Line 3,442 ⟶ 4,002:
}
println("all one")
}</
{{out}}
Line 3,467 ⟶ 4,027:
=={{header|Lua}}==
<
function sternBrocot (n)
local sbList, pos, c = {1, 1}, 2
Line 3,515 ⟶ 4,075:
for i = 1, 10 do print("\t" .. i, findFirst(sb, i)) end
print("\nTask 4: " .. findFirst(sb, 100))
print("\nTask 5: " .. task5(sb))</
{{out}}
<pre>Task 2: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
Line 3,535 ⟶ 4,095:
Task 5: PASS</pre>
=={{header|
<syntaxhighlight lang="macro11"> .TITLE STNBRC
.MCALL .TTYOUT,.EXIT
AMOUNT = ^D1200
STNBRC::JSR PC,GENSEQ
; PRINT FIRST 15
MOV #FST15,R1
JSR PC,PRSTR
MOV #STERN+2,R3
MOV #^D15,R4
1$: MOV (R3)+,R0
JSR PC,PR0
SOB R4,1$
MOV #NEWLINE,R1
JSR PC,PRSTR
; PRINT FIRST OCCURRENCE OF 1..10 AND 100
MOV #FSTOCC,R1
JSR PC,PRSTR
MOV #1,R3
2$: JSR PC,PRFST
INC R3
CMP R3,#^D10
BLE 2$
MOV #^D100,R3
JSR PC,PRFST
MOV #NEWLIN,R1
JSR PC,PRSTR
; CHECK GCDS OF ADJACENT PAIRS UP TO 1000
MOV #CHKGCD,R1
JSR PC,PRSTR
MOV #STERN+2,R2
MOV #^D999,R5
MOV (R2)+,R3
3$: MOV R3,R4
MOV (R2)+,R3
MOV R3,R0
MOV R4,R1
JSR PC,GCD
DEC R0
BNE 4$
SOB R5,3$
MOV #ALL1,R1
BR 5$
4$: MOV #NOTAL1,R1
5$: JSR PC,PRSTR
.EXIT
FST15: .ASCIZ /FIRST 15: /
FSTOCC: .ASCIZ /FIRST OCCURRENCES:/<15><12>
ATWD: .ASCIZ /AT /
CHKGCD: .ASCIZ /CHECKING GCDS OF ADJACENT PAIRS... /
NOTAL1: .ASCII /NOT /
ALL1: .ASCIZ /ALL 1./
NEWLIN: .BYTE 15,12,0
.EVEN
; GENERATE STERN-BROCOT SEQUENCE
GENSEQ: MOV #1,R0
MOV R0,STERN+2
MOV R0,STERN+4
MOV #STERN+<2*AMOUNT>,R5
MOV #STERN+2,R0
MOV #STERN+6,R1
MOV (R0)+,R2
1$: MOV R2,R3
MOV (R0)+,R2
MOV R2,R4
ADD R3,R4
MOV R4,(R1)+
MOV R2,(R1)+
CMP R1,R5
BLT 1$
RTS PC
; LET R0 = FIRST OCCURRENCE OF R3 IN SEQUENCE
FNDFST: MOV #STERN,R0
1$: CMP (R0)+,R3
BNE 1$
SUB #STERN+2,R0
ASR R0
RTS PC
; PRINT FIRST OCC. OF <R3>
PRFST: MOV R3,R0
JSR PC,PR0
MOV #ATWD,R1
JSR PC,PRSTR
JSR PC,FNDFST
JSR PC,PR0
MOV #NEWLIN,R1
JMP PRSTR
; LET R0 = GCD(R0,R1)
GCD: CMP R0,R1
BLT 1$
BGT 2$
RTS PC
1$: SUB R0,R1
BR GCD
2$: SUB R1,R0
BR GCD
; PRINT NUMBER IN R0 AS DECIMAL
PR0: MOV #4$,R1
1$: MOV #-1,R2
2$: INC R2
SUB #12,R0
BCC 2$
ADD #72,R0
MOVB R0,-(R1)
MOV R2,R0
BNE 1$
3$: MOVB (R1)+,R0
.TTYOUT
BNE 3$
RTS PC
.ASCII /...../
4$: .ASCIZ / /
.EVEN
; PRINT STRING IN R1
PRSTR: MOVB (R1)+,R0
.TTYOUT
BNE PRSTR
RTS PC
; STERN-BROCOT BUFFER
STERN: .BLKW AMOUNT+1
.END STNBRC</syntaxhighlight>
{{out}}
<pre>FIRST 15: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
FIRST OCCURRENCES:
1 AT 1
2 AT 3
3 AT 5
4 AT 9
5 AT 11
6 AT 33
7 AT 19
8 AT 21
9 AT 35
10 AT 39
100 AT 1179
CHECKING GCDS OF ADJACENT PAIRS... ALL 1.</pre>
=={{header|MAD}}==
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER
VECTOR VALUES FRST15 = $20HFIRST 15 NUMBERS ARE*$
VECTOR VALUES FRSTAT = $6HFIRST ,I3,S1,11HAPPEARS AT ,I4*$
Line 3,567 ⟶ 4,274:
SCAN WHENEVER N .E. STERN(K), FUNCTION RETURN K
END OF FUNCTION
END OF PROGRAM</
{{out}}
Line 3,600 ⟶ 4,307:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
Do[
sb = sb~Join~{Total@sb[[i - 1 ;; i]], sb[[i]]}
Line 3,609 ⟶ 4,316:
Flatten[FirstPosition[sb, #] & /@ Range[10]]
First@FirstPosition[sb, 100]
AllTrue[Partition[Take[sb, 1000], 2, 1], Apply[GCD] /* EqualTo[1]]</
{{out}}
<pre>{1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4}
Line 3,615 ⟶ 4,322:
1179
True</pre>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout (lay
["First 15: " ++ show first15,
"Indices of first 1..10: " ++ show idx10,
"Index of first 100: " ++ show idx100,
"The GCDs of the first 1000 pairs are all 1: " ++ show allgcd])]
first15 :: [num]
first15 = take 15 stern
idx10 :: [num]
idx10 = [find num stern | num<-[1..10]]
idx100 :: num
idx100 = find 100 stern
allgcd :: bool
allgcd = and [gcd a b = 1 | (a, b) <- take 1000 (zip2 stern (tl stern))]
|| Stern-Brocot sequence
stern :: [num]
stern = 1 : 1 : concat (map consider (zip2 stern (tl stern)))
where consider (prev,item) = [prev + item, item]
|| Supporting functions
gcd :: num->num->num
gcd a 0 = a
gcd a b = gcd b (a mod b)
find :: *->[*]->num
find item = find' 1
where find' idx [] = 0
find' idx (a:as) = idx, if a = item
= find' (idx + 1) as, otherwise</syntaxhighlight>
{{out}}
<pre>First 15: [1,1,2,1,3,2,3,1,4,3,5,2,5,3,4]
Indices of first 1..10: [1,3,5,9,11,33,19,21,35,39]
Index of first 100: 1179
The GCDs of the first 1000 pairs are all 1: True</pre>
=={{header|Modula-2}}==
<
FROM InOut IMPORT WriteString, WriteCard, WriteLn;
Line 3,691 ⟶ 4,440:
WriteString("The GCD of every pair of adjacent elements is 1.");
WriteLn;
END SternBrocot.</
{{out}}
<pre>First 15 numbers: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
Line 3,711 ⟶ 4,460:
We use an iterator and store the values in a sequence. To reduce memory usage, we could replace the sequence with a deque and pop the previous value at each round. But it’s no worth to complete the task.
<
iterator sternBrocot(): (int, int) =
Line 3,767 ⟶ 4,516:
echo "Found two successive terms at index: ", index
else:
echo "All consecutive terms up to the 1000th member have a GCD equal to one."</
{{out}}
Line 3,786 ⟶ 4,535:
All consecutive terms up to the 1000th member have a GCD equal to one.</pre>
=={{header|
<syntaxhighlight lang="ocaml">let seq_stern_brocot =
let rec next x xs () =
match xs () with
| Seq.Nil -> assert false
| Cons (x', xs') -> Seq.Cons (x' + x, Seq.cons x' (next x' xs'))
in
let rec tail () = Seq.Cons (1, next 1 tail) in
Seq.cons 1 tail</syntaxhighlight>
;<nowiki>Tests:</nowiki>
<syntaxhighlight lang="ocaml">let rec gcd a = function
| 0 -> a
| b -> gcd b (a mod b)
let seq_index_of el =
let rec next i sq =
match sq () with
| Seq.Nil -> 0
| Cons (e, sq') -> if e = el then i else next (succ i) sq'
in
next 1
let seq_map_pairwise f sq =
match sq () with
| Seq.Nil -> Seq.empty
| Cons (_, sq') -> Seq.map2 f sq sq'
let () =
seq_stern_brocot |> Seq.take 15 |> Seq.iter (Printf.printf " %u") |> print_newline
and () =
List.iter
(fun n -> seq_stern_brocot |> seq_index_of n |> Printf.printf " %u@%u" n)
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 100]
|> print_newline
and () =
seq_stern_brocot |> Seq.take 1000 |> seq_map_pairwise gcd |> Seq.for_all ((=) 1)
|> Printf.printf " %B\n"</syntaxhighlight>
{{out}}
<pre>
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
1@1 2@3 3@5 4@9 5@11 6@33 7@19 8@21 9@35 10@39 100@1179
true
</pre>
=={{header|Oforth}}==
<syntaxhighlight lang="oforth">: stern(n)
| l i |
ListBuffer new dup add(1) dup add(1) dup ->l
Line 3,794 ⟶ 4,586:
n 2 mod ifFalse: [ dup removeLast drop ] dup freeze ;
stern(10000) Constant new: Sterns</
{{out}}
Line 3,825 ⟶ 4,617:
{{Works with|PARI/GP|2.7.4 and above}}
<
\\ Stern-Brocot sequence
\\ 5/27/16 aev
Line 3,853 ⟶ 4,645:
if(j==1, print("Yes"), print("No"));
}
</
{{Output}}
Line 3,865 ⟶ 4,657:
=={{header|Pascal}}==
{{works with|Free Pascal}}
<
{$IFDEF FPC}
{$MODE DELPHI}
Line 3,951 ⟶ 4,743:
writeln('GCD-test is O.K.');
setlength(seq,0);
end.</
1 @ 1,2 @ 3,3 @ 5,4 @ 9,5 @ 11,6 @ 33,7 @ 38,8 @ 42,9 @ 47,10 @ 57
100 @ 1179
Line 3,957 ⟶ 4,749:
=={{header|Perl}}==
<
use warnings;
Line 3,992 ⟶ 4,784:
($a, $b) = ($b, $generator->());
}
}</
{{out}}
<pre>1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
Line 4,008 ⟶ 4,800:
A slightly different method:{{libheader|ntheory}}
<
sub stern_diatomic {
Line 4,026 ⟶ 4,818:
print "The first 999 consecutive pairs are ",
(vecsum( map { gcd(stern_diatomic($_),stern_diatomic($_+1)) } 1..999 ) == 999)
? "all coprime.\n" : "NOT all coprime!\n";</
{{out}}
<pre>First fifteen: [1 1 2 1 3 2 3 1 4 3 5 2 5 3 4]
Line 4,034 ⟶ 4,826:
=={{header|Phix}}==
<!--<
<span style="color: #004080;">sequence</span> <span style="color: #000000;">sb</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;">1</span><span style="color: #0000FF;">}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
Line 4,076 ⟶ 4,868:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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;">"max gcd:%d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">maxgcd</span><span style="color: #0000FF;">})</span>
<!--</
{{Out}}
<pre>
Line 4,088 ⟶ 4,880:
{{trans|C}}
Using the <tt>gcd</tt> function defined at ''[[Greatest_common_divisor#PicoLisp]]'':
<
(let (A 1 B 0)
(while (gt0 N)
Line 4,104 ⟶ 4,896:
(for (L Lst (cdr L) (cddr L))
(test 1 (gcd (car L) (cadr L))) )
(prinl "All consecutive pairs are relative prime!") )</
{{out}}
<pre>
Line 4,123 ⟶ 4,915:
=={{header|PL/I}}==
<
%replace MAX by 1200;
declare S(1:MAX) fixed;
Line 4,170 ⟶ 4,962:
end;
put skip list('All GCDs of adjacent pairs are 1.');
end sternBrocot;</
{{out}}
<pre>First 15 elements: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
Line 4,187 ⟶ 4,979:
=={{header|PL/M}}==
<
/* FIND LOCATION OF FIRST ELEMENT IN ARRAY */
FIND$FIRST: PROCEDURE (ARR, EL) ADDRESS;
Line 4,274 ⟶ 5,066:
CALL PRINT(.'ALL GCDS ARE 1$');
CALL BDOS(0,0);
EOF</
{{out}}
<pre>FIRST 15 ELEMENTS: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
Line 4,291 ⟶ 5,083:
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
# An iterative approach
function iter_sb($count = 2000)
Line 4,320 ⟶ 5,112:
'GCD = 1 for first 1000 members: {0}' -f $gcd
}
</syntaxhighlight>
{{out}}
Line 4,355 ⟶ 5,147:
=={{header|PureBasic}}==
<
Define.i i
Line 4,405 ⟶ 5,197:
EndIf
Input()</
{{out}}
<pre>Stern-Brocot_sequence
Line 4,426 ⟶ 5,218:
=={{header|Python}}==
===Python: procedural===
<
"""\
Generates members of the stern-brocot series, in order, returning them when the predicate becomes false
Line 4,461 ⟶ 5,253:
s = stern_brocot(lambda series: len(series) < n_gcd)[:n_gcd]
assert all(gcd(prev, this) == 1
for prev, this in zip(s, s[1:])), 'A fraction from adjacent terms is reducible'</
{{out}}
Line 4,484 ⟶ 5,276:
See the [[Talk:Stern-Brocot_sequence#deque_over_list.3F|talk page]] for how a deque was selected over the use of a straightforward list'
<
>>> from collections import deque
>>> from fractions import gcd
Line 4,505 ⟶ 5,297:
>>> all(gcd(p, t) == 1 for p, t in islice(zip(prev, this), 1000))
True
>>> </
===Python: Composing pure (curried) functions===
Line 4,511 ⟶ 5,303:
Composing and testing a Stern-Brocot function by composition of generic and reusable functional abstractions (curried for more flexible nesting and rearrangement).
{{Works with|Python|3.7}}
<
import math
Line 4,688 ⟶ 5,480:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>[1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]
Line 4,694 ⟶ 5,486:
[(100, 1179)]
True</pre>
=={{header|Quackery}}==
<syntaxhighlight lang="quackery"> [ [ dup while
tuck mod again ]
drop abs ] is gcd ( n n --> n )
[ 2dup peek
dip [ 1+ 2dup peek ]
over + swap join
swap dip join ] is two-terms ( [ n --> [ n )
' [ 1 1 ] 0
8 times two-terms
over 15 split drop
witheach [ echo sp ] cr
[ two-terms
over -2 peek 100 = until ]
drop
10 times
[ i^ 1+ over find 1+ echo sp ] cr
dup size 1 - echo cr
false swap
behead swap witheach
[ tuck gcd 1 != if
[ dip not conclude ] ]
drop iff
[ say "Reducible pair found." ]
else
[ say "No reducible pairs found." ]</syntaxhighlight>
{{out}}
<pre>1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
1 3 5 9 11 33 19 21 35 39
1179
No reducible pairs found.
</pre>
=={{header|R}}==
Line 4,701 ⟶ 5,530:
{{libheader|pracma}}
<syntaxhighlight lang="rsplus">
## Stern-Brocot sequence
## 12/19/16 aev
Line 4,724 ⟶ 5,553:
if(j==1) {cat(" *** All GCDs=1!\n")} else {cat(" *** All GCDs!=1??\n")}
}
</
{{Output}}
Line 4,742 ⟶ 5,571:
As with the previous solution, we have used a library for our gcd function. In this case, we have used gmp.
<
{
sternNums <- c(
i <- 2
while((endIndex <- length(sternNums)) < n)
{
#To show off R's vectorization, the following line is deliberately terse.
Line 4,753 ⟶ 5,582:
#Note that we do not have to initialize a big sternNums array to do this.
#True to the algorithm, the new entries are appended to the end of the old sequence.
sternNums[endIndex + c(1, 2)] <- c(sum(sternNums[c(i - 1, i)]), sternNums[i])
i <- i + 1
}
sternNums[
}
#N=5000 was picked arbitrarily. The code runs very fast regardless of this number being much more than we need.
firstFiveThousandTerms <- genNStern(5000)
match(1:10, firstFiveThousandTerms)
match(100, firstFiveThousandTerms)
all(sapply(1:999, function(i) gmp::gcd(firstFiveThousandTerms[i], firstFiveThousandTerms[i + 1])) == 1)</
{{Output}}
<pre>> firstFiveThousandTerms <- genNStern(5000)
> match(1:10, firstFiveThousandTerms)
[1] 1 3 5 9 11 33 19 21 35 39
> match(100, firstFiveThousandTerms)
[1] 1179
> all(sapply(1:999, function(i) gmp::gcd(firstFiveThousandTerms[i], firstFiveThousandTerms[i + 1])) == 1)
[1] TRUE</pre>
=={{header|Racket}}==
<syntaxhighlight lang="racket">#lang racket
;; OEIS Definition
;; A002487
Line 4,811 ⟶ 5,639:
(for/first ((i (in-range 1 1000))
#:unless (= 1 (gcd (Stern-Brocot i) (Stern-Brocot (add1 i))))) #t)
(display "\tdidn't find gcd > (or otherwise ≠) 1"))</
{{out}}
Line 4,837 ⟶ 5,665:
(formerly Perl 6)
{{works with|rakudo|2017-03}}
<syntaxhighlight lang="raku"
put @Stern-Brocot[^15];
Line 4,845 ⟶ 5,673:
}
say so 1 == all map ^1000: { [gcd] @Stern-Brocot[$_, $_ + 1] }</
{{out}}
<pre>1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
Line 4,861 ⟶ 5,689:
True</pre>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
, <Stern 1300>: e.Seq
= <Prout 'First 15: ' <Take 15 e.Seq>>
<ForEach (<Iota 1 10>) ShowFirst e.Seq>
<ShowFirst 100 e.Seq>
<Prout <GcdPairCheck <Take 1000 e.Seq>>>;
};
Stern {
s.N = <Stern <- s.N 2> (1) 1>;
0 (e.X) e.Y = e.X e.Y;
s.N (e.X s.P) s.C e.Y,
<- s.N 1>: s.Rem,
<+ s.P s.C>: s.CSum
= <Stern s.Rem (e.X s.P s.C) e.Y s.CSum s.C>;
};
Take {
0 e.X = ;
s.N s.I e.X = s.I <Take <- s.N 1> e.X>;
};
FindFirst {
s.I e.X = <FindFirst (1) s.I e.X>;
(s.L) s.I s.I e.X = s.L;
(s.L) s.I s.J e.X = <FindFirst (<+ s.L 1>) s.I e.X>;
};
ShowFirst {
s.I e.X, <FindFirst s.I e.X>: s.N = <Prout 'First ' s.I 'at ' s.N>;
};
ForEach {
() s.F e.Arg = ;
(s.I e.X) s.F e.Arg = <Mu s.F s.I e.Arg> <ForEach (e.X) s.F e.Arg>;
};
Iota {
s.From s.To = <Iota s.From s.To s.From>;
s.From s.To s.To = s.To;
s.From s.To s.Cur = s.Cur <Iota s.From s.To <+ s.Cur 1>>;
};
Gcd {
s.N 0 = s.N;
s.N s.M = <Gcd s.M <Mod s.N s.M>>;
};
GcdPairCheck {
s.A s.B e.X, <Gcd s.A s.B>: 1
= <GcdPairCheck s.B e.X>;
s.A s.B e.X, <Gcd s.A s.B>: s.N
= 'The GCD of ' <Symb s.A> ' and ' <Symb s.B> ' is ' <Symb s.N>;
e.X = 'The GCDs of all adjacent pairs are 1.';
};</syntaxhighlight>
{{out}}
<pre>First 15: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
First 1 at 1
First 2 at 3
First 3 at 5
First 4 at 9
First 5 at 11
First 6 at 33
First 7 at 19
First 8 at 21
First 9 at 35
First 10 at 39
First 100 at 1179
The GCDs of all adjacent pairs are 1.</pre>
=={{header|REXX}}==
<
parse arg N idx fix chk . /*get optional arguments from the C.L. */
if N=='' | N=="," then N= 15 /*Not specified? Then use the default.*/
Line 4,911 ⟶ 5,809:
end /*k*/
if f==0 then return subword($, 1, h)
return $</
{{out|output|text= when using the default inputs:}}
<pre>
Line 4,937 ⟶ 5,835:
=={{header|Ring}}==
<
# Project : Stern-Brocot sequence
Line 4,991 ⟶ 5,889:
end
return gcd
</syntaxhighlight>
Output:
<pre>
Line 5,008 ⟶ 5,906:
Correct: The first 999 consecutive pairs are relative prime!
</pre>
=={{header|RPL}}==
Task 1 is done by applying the algorithm explained above.
Other requirements are based on Mike Stay's formula for OEIS AA002487:
a(n) = a(n-2) + a(n-1) - 2*(a(n-2) mod a(n-1))
which avoids keeping a huge subset of the sequence in memory
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
{ 1 1 } 1
'''WHILE''' OVER SIZE 4 PICK < '''REPEAT'''
GETI ROT ROT DUP2 GET 4 ROLL +
ROT SWAP + SWAP
DUP2 GET ROT SWAP + SWAP
'''END''' ROT DROP2
≫ ‘'''TASK1'''’ STO
≪
0 1
2 4 ROLL '''START'''
DUP2 + LAST MOD 2 * - ROT DROP '''NEXT'''
SWAP DROP
≫ ‘'''STERN'''’ STO
≪ 1
'''WHILE''' DUP '''STERN''' 3 PICK ≠ '''REPEAT''' 1 + '''END''' R→C
≫ ‘'''WHEN'''’ STO
|
'''TASK1''' ''( n -- {SB(1)..SB(n) )''
initialize stack with SB(1), SB(2) and pointer i
loop until SB(n) reached
get SB(i)+SB(i+1)
add to list
add SB(i+1) to list
clean stack
'''STERN''' ''( n -- SB(n) )''
initialize stack with SB(0), SB(1)
loop n-2 times
SB(i)=SB(i-1)+SB(i-2)-2*(SB(i-2) mod SB(i-1))
clean stack
'''WHEN''' ''( m -- (n,SB(n)) )'' with SB(n) = m
loop until found
|}
{{in}}
<pre>
15 TASK1
{ } 1 10 FOR n n WHEN + NEXT
100 WHEN
</pre>
{{out}}
<pre>
3: { 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 }
2: { (1,1) (2,3) (3,5) (4,9) (5,11) (6,33) (7,19) (8,21) (9,35) (10,39) }
1: (100,1179)
</pre>
===Faster version for big values of n===
We use here the fact that
SB(2^k) = 1 and SB(2^k + 1) = k+1 for any k>0
which can be easily demonstrated by using the definition of the fusc sequence, identical to the Stern-Brocot sequence (OEIS AA002487).
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
'''IF''' DUP 4 < '''THEN''' 0 1
'''ELSE'''
DUP LN 2 LN / IP 2 OVER ^
ROT SWAP - 1 ROT 1 +
'''END'''
≫ ‘'''Offset'''’ STO
≪
'''Offset'''
2 4 ROLL '''START'''
DUP2 + LAST MOD 2 * - ROT DROP '''NEXT'''
SWAP DROP
≫ ‘'''STERN'''’ STO
|
'''Offset''' ''( n -- 1 k+1 offset )''
start at the beginning for small n values
otherwise
get k with 2^k ≤ n
initialize stack to 1, k+1, n-2^k
'''STERN''' ''( n -- SB(n) )''
initialize stack
loop n-2 times
SB(i)=SB(i-1)+SB(i-2)-2*(SB(i-2) mod SB(i-1))
clean stack
|}
2147484950 '''STERN'''
1: 1385
=={{header|Ruby}}==
{{works with|Ruby|2.1}}
<
return enum_for :sb unless block_given?
a=[1,1]
Line 5,030 ⟶ 6,033:
else
puts "Whoops, not all GCD's are 1!"
end</
{{out}}
Line 5,050 ⟶ 6,053:
=={{header|Scala}}==
<
BigInt("1") #::
BigInt("1") #::
Line 5,068 ⟶ 6,071:
(sbSeq zip sbSeq.tail).take(1000).forall{ case (a,b) => a.gcd(b) == 1 } )
}
</syntaxhighlight>
{{out}}
Line 5,089 ⟶ 6,092:
</pre>
=={{header|Scheme}}==
{{works with|Chez Scheme}}
'''The Function'''
<syntaxhighlight lang="scheme">; Recursive function to return the Nth Stern-Brocot sequence number.
(define stern-brocot
(lambda (n)
(cond
((<= n 0)
0)
((<= n 2)
1)
((even? n)
(stern-brocot (/ n 2)))
(else
(let ((earlier (/ (1+ n) 2)))
(+ (stern-brocot earlier) (stern-brocot (1- earlier))))))))</syntaxhighlight>
'''The Task'''
<syntaxhighlight lang="scheme">; Show the first 15 Stern-Brocot sequence numbers.
(printf "First 15 Stern-Brocot numbers:")
(do ((index 1 (1+ index)))
((> index 15))
(printf " ~a" (stern-brocot index)))
(newline)
; Show the indices of where the numbers 1 to 10 first appear in the Stern-Brocot sequence.
(let ((indices (make-vector 11 #f))
(found 0))
(do ((index 1 (1+ index)))
((>= found 10))
(let ((number (stern-brocot index)))
(when (and (<= number 10) (not (vector-ref indices number)))
(vector-set! indices number index)
(set! found (1+ found)))))
(printf "Indices of where the numbers 1 to 10 first appear:")
(do ((index 1 (1+ index)))
((> index 10))
(printf " ~a" (vector-ref indices index))))
(newline)
; Show the index of where the number 100 first appears in the Stern-Brocot sequence.
(do ((index 1 (1+ index)) (found #f))
(found)
(let ((number (stern-brocot index)))
(when (= number 100)
(printf "Index where the number 100 first appears: ~a~%" index)
(set! found #t))))
; Check that the GCD of all two consecutive members up to the 1000th member is always one.
(let ((any-bad #f)
(gcd (lambda (a b)
(if (= b 0)
a
(gcd b (remainder a b))))))
(do ((index 1 (1+ index)))
((> index 1000))
(let ((sbgcd (gcd (stern-brocot index) (stern-brocot (1+ index)))))
(when (not (= 1 sbgcd))
(printf "GCD of Stern-Brocot ~a and ~a+1 is ~a -- Not 1~%" index index sbgcd)
(set! any-bad #t))))
(when (not any-bad)
(printf "GCDs of all Stern-Brocot consecutive pairs from 1 to 1000 are 1~%")))</syntaxhighlight>
{{out}}
<pre>First 15 Stern-Brocot numbers: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
Indices of where the numbers 1 to 10 first appear: 1 3 5 9 11 33 19 21 35 39
Index where the number 100 first appears: 1179
GCDs of all Stern-Brocot consecutive pairs from 1 to 1000 are 1</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program stern_brocot_sequence;
s := stern(1200);
print("First 15 elements:", s(1..15));
loop for n in [1..10] with 100 do
if exists k = s(i) | k = n then
print("First", n, "at", i);
end if;
end loop;
gcds := [gcd(s(i-1), s(i)) : i in [2..1000]];
if exists g = gcds(i) | g /= 1 then
print("The GCD of the pair at", i, "is not 1.");
else
print("All GCDs of consecutive pairs up to 1000 are 1.");
end if;
proc stern(n);
s := [1, 1];
loop for i in [2..n div 2] do
s(i*2-1) := s(i) + s(i-1);
s(i*2) := s(i);
end loop;
return s;
end proc;
proc gcd(a,b);
loop while b/=0 do
[a, b] := [b, a mod b];
end loop;
return a;
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>First 15 elements: [1 1 2 1 3 2 3 1 4 3 5 2 5 3 4]
First 1 at 1
First 2 at 3
First 3 at 5
First 4 at 9
First 5 at 11
First 6 at 33
First 7 at 19
First 8 at 21
First 9 at 35
First 10 at 39
First 100 at 1179
All GCDs of consecutive pairs up to 1000 are 1.</pre>
=={{header|Sidef}}==
{{trans|Perl}}
<
func stern_brocot {
var list = [1, 1]
Line 5,124 ⟶ 6,249:
} * 1000
say "All GCD's are 1"</
{{out}}
<pre>
Line 5,143 ⟶ 6,268:
=={{header|Snobol}}==
<syntaxhighlight lang="snobol">* GCD function
DEFINE('GCD(A,B)') :(GCD_END)
GCD GCD = A
Line 5,188 ⟶ 6,312:
GCDFAIL OUTPUT = "GCD is not 1 at " IX "."
END</
{{out}}
Line 5,205 ⟶ 6,329:
First 100 at 1179
All GCDs are 1.</pre>
=={{header|Swift}}==
<syntaxhighlight lang="swift">struct SternBrocot: Sequence, IteratorProtocol {
private var seq = [1, 1]
Line 5,248 ⟶ 6,370:
let gcdIsOne = zip(firstThousand, firstThousand.dropFirst()).allSatisfy({ gcd($0.0, $0.1) == 1 })
print("GCDs of all two consecutive members are \(gcdIsOne ? "" : "not")one")</
{{out}}
Line 5,266 ⟶ 6,388:
=={{header|Tcl}}==
<
#!/usr/bin/env tclsh
#
Line 5,371 ⟶ 6,493:
main
</syntaxhighlight>
{{Out}}
<pre>
Line 5,394 ⟶ 6,516:
=={{header|VBScript}}==
<
i = 1 'considered
j = 2 'precedent
Line 5,433 ⟶ 6,555:
End If
Next
End Function</
{{Out}}
<pre>First 15: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4
Line 5,450 ⟶ 6,572:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Imports System.Collections.Generic
Imports System.Linq
Line 5,478 ⟶ 6,600:
" series up to the {0}th item is {1}always one.", max, If(good, "", "not "))
End Sub
End Module</
{{out}}
<pre>The first 15 items In the Stern-Brocot sequence: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4
Line 5,502 ⟶ 6,624:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var sbs = [1, 1]
Line 5,574 ⟶ 6,696:
p = p + 2
}
System.print("all one.")</
{{out}}
Line 5,599 ⟶ 6,721:
=={{header|zkl}}==
<
{ Walker(fcn(sb,n){ a,b:=sb; sb.append(a+b,b); sb.del(0); a }.fp(L(1,1))) }
Line 5,609 ⟶ 6,731:
[1..].zip(SB()).filter1(fcn(sb){ 100==sb[1] }).println();
sb:=SB(); do(500){ if(sb.next().gcd(sb.next())!=1) println("Oops") }</
{{out}}
<pre>
|