Stern-Brocot sequence

Stern-Brocot sequence
You are encouraged to solve this task according to the task description, using any language you may know.

For this task, the Stern-Brocot sequence is to be generated by an algorithm similar to that employed in generating the Fibonacci sequence.

1. The first and second members of the sequence are both 1:
•     1, 1
2. Start by considering the second member of the sequence
3. Sum the considered member of the sequence and its precedent, (1 + 1) = 2, and append it to the end of the sequence:
•     1, 1, 2
4. Append the considered member of the sequence to the end of the sequence:
•     1, 1, 2, 1
5. Consider the next member of the series, (the third member i.e. 2)
6. GOTO 3
•         ─── Expanding another loop we get: ───
7. Sum the considered member of the sequence and its precedent, (2 + 1) = 3, and append it to the end of the sequence:
•     1, 1, 2, 1, 3
8. Append the considered member of the sequence to the end of the sequence:
•     1, 1, 2, 1, 3, 2
9. Consider the next member of the series, (the fourth member i.e. 1)

• 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 first appear in the sequence.
• 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 1000th member, is always one.

Ref

11l

Translation of: Python
```F stern_brocot(predicate = series -> series.len < 20)
V sb = [1, 1]
V i = 0
L predicate(sb)
sb [+]= [sum(sb[i .< i + 2]), sb[i + 1]]
i++
R sb

V n_first = 15
print(("The first #. values:\n  ".format(n_first))‘ ’stern_brocot(series -> series.len < :n_first)[0 .< n_first])
print()

V n_max = 10
L(n_occur) Array(1 .. n_max) [+] [100]
print((‘1-based index of the first occurrence of #3 in the series:’.format(n_occur))‘ ’(stern_brocot(series -> @n_occur !C series).index(n_occur) + 1))
print()

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’)```
Output:
```The first 15 values:
[1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]

1-based index of the first occurrence of   1 in the series: 1
1-based index of the first occurrence of   2 in the series: 3
1-based index of the first occurrence of   3 in the series: 5
1-based index of the first occurrence of   4 in the series: 9
1-based index of the first occurrence of   5 in the series: 11
1-based index of the first occurrence of   6 in the series: 33
1-based index of the first occurrence of   7 in the series: 19
1-based index of the first occurrence of   8 in the series: 21
1-based index of the first occurrence of   9 in the series: 35
1-based index of the first occurrence of  10 in the series: 39
1-based index of the first occurrence of 100 in the series: 1179
```

360 Assembly

Translation of: Fortran
```*        Stern-Brocot sequence     - 12/03/2019
STERNBR  CSECT
USING  STERNBR,R13        base register
B      72(R15)            skip savearea
DC     17F'0'             savearea
SAVE   (14,12)            save previous context
LA     R4,SB+2            k=2; @sb(k)
LA     R2,SB+2            i=1; @sb(k-i)
LA     R3,SB+0            j=2; @sb(k-j)
LA     R1,NN/2            loop counter
LOOP     LA     R4,2(R4)             @sb(k)++
LH     R0,0(R2)             sb(k-i)
AH     R0,0(R3)             sb(k-i)+sb(k-j)
STH    R0,0(R4)             sb(k)=sb(k-i)+sb(k-j)
LA     R3,2(R3)             @sb(k-j)++
LA     R4,2(R4)             @sb(k)++
LH     R0,0(R3)             sb(k-j)
STH    R0,0(R4)             sb(k)=sb(k-j)
LA     R2,2(R2)             @sb(k-i)++
BCT    R1,LOOP            end loop
LA     R9,15              n=15
MVC    PG(5),=CL80'FIRST'
XDECO  R9,XDEC            edit n
MVC    PG+5(3),XDEC+9     output n
XPRNT  PG,L'PG            print buffer
LA     R10,PG             @pg
LA     R6,1               i=1
DO WHILE=(CR,R6,LE,R9)      do i=1 to n
LR     R1,R6                i
SLA    R1,1                 ~
LH     R2,SB-2(R1)          sb(i)
XDECO  R2,XDEC              edit sb(i)
MVC    0(4,R10),XDEC+8      output sb(i)
LA     R10,4(R10)           @pg+=4
LA     R6,1(R6)             i++
ENDDO    ,                  enddo i
XPRNT  PG,L'PG            print buffer
LA     R7,1                j=1
DO WHILE=(C,R7,LE,=A(11))   do j=1 to 11
IF C,R7,EQ,=F'11' THEN        if j=11 then
LA     R7,100                 j=100
ENDIF    ,                    endif
LA     R6,1                 i=1
DO WHILE=(C,R6,LE,=A(NN))     do i=1 to nn
LR     R1,R6                  i
SLA    R1,1                   ~
LH     R2,SB-2(R1)            sb(i)
CR     R2,R7                  if sb(i)=j
BE     EXITI                  then leave i
LA     R6,1(R6)               i++
ENDDO    ,                    enddo i
EXITI    MVC    PG,=CL80'FIRST INSTANCE OF'
XDECO  R7,XDEC              edit j
MVC    PG+17(4),XDEC+8      output j
MVC    PG+21(7),=C' IS AT '
XDECO  R6,XDEC              edit i
MVC    PG+28(4),XDEC+8      output i
XPRNT  PG,L'PG              print buffer
LA     R7,1(R7)             j++
ENDDO    ,                  enddo j
L      R13,4(0,R13)       restore previous savearea pointer
RETURN (14,12),RC=0       restore registers from calling sav
LTORG
NN       EQU    2400               nn
PG       DC     CL80' '            buffer
XDEC     DS     CL12               temp for xdeco
SB       DC     (NN)H'1'           sb(nn)
REGEQU
END    STERNBR```
Output:
```FIRST 15
1   1   2   1   3   2   3   1   4   3   5   2   5   3   4
FIRST INSTANCE OF   1 IS AT    1
FIRST INSTANCE OF   2 IS AT    3
FIRST INSTANCE OF   3 IS AT    5
FIRST INSTANCE OF   4 IS AT    9
FIRST INSTANCE OF   5 IS AT   11
FIRST INSTANCE OF   6 IS AT   33
FIRST INSTANCE OF   7 IS AT   19
FIRST INSTANCE OF   8 IS AT   21
FIRST INSTANCE OF   9 IS AT   35
FIRST INSTANCE OF  10 IS AT   39
FIRST INSTANCE OF 100 IS AT 1179
```

The nice part is the coding of the sequense:

```    k=2; i=1; j=2;
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     R4,SB+2            k=2; @sb(k)
LA     R2,SB+2            i=1; @sb(k-i)
LA     R3,SB+0            j=2; @sb(k-j)
LA     R1,NN/2            k=nn/2  'loop counter
LOOP     LA     R4,2(R4)             @sb(k)++
LH     R0,0(R2)             sb(k-i)
AH     R0,0(R3)             sb(k-i)+sb(k-j)
STH    R0,0(R4)             sb(k)=sb(k-i)+sb(k-j)
LA     R3,2(R3)             @sb(k-j)++
LA     R4,2(R4)             @sb(k)++
LH     R0,0(R3)             sb(k-j)
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```

8080 Assembly

```puts:	equ	9	; CP/M syscall to print a string
org	100h
;;;	Generate the first 1200 elements of the Stern-Brocot sequence
lxi	b,600	; 2 elements generated per loop
lxi	h,seq
mov	e,m	; Initialization
inx	h
push	h	; Save considered member pointer
inx	h	; Insertion pointer
genseq:	xthl		; Load considered member pointer
mov	d,e	; D = predecessor
mov	e,m	; E = considered member
inx	h	; Point at next considered member
mov	a,d	; A = sum of both members
mov	m,a	; Append the sum
inx	h
mov	m,e	; Append the considered member
inx	h
dcx 	b	; Decrement counter
mov	a,b	; Zero?
ora	c
jnz	genseq	; If not, generate next members of sequence
pop	h	; Remove pointer from stack
;;;	Print first 15 members of sequence
lxi	d,seq
mvi	b,15	; 15 members
mvi	h,0
p15:	ldax	d	; Get current member
mov	l,a
call	prhl	; Print member
inx	d	; Increment pointer
dcr	b	; Decrement counter
jnz	p15	; If not zero, print another one
lxi	d,nl
mvi	c,puts
call	5
;;;	Print indices of first occurrence of 1..10
lxi	b,010Ah	; B = number, C = counter
call	fnext
;;;	Print index of first occurrence of 100
lxi	b,6401h
call	fnext
;;;	Check if the GCD of first 1000 consecutive elements is 0
xra	a	; Zero out 1001th element as end marker
sta	seq+1000
lxi	h,seq	; Start of array
mov	e,m
inx	h
gcdchk:	mov	d,e	; (D,E) = next pair
mov	e,m
inx	h
mov	a,e
mov	b,d
ana	a	; Reached the end?
jz	done
call	gcd	; If not, check GCD
dcr	a	; Check that it is 1
jz	gcdchk	; If so, check next pair
push	h	; GCD not 1 - save pointer
lxi	d,gcdn	; Print message
mvi	c,puts
call	5
pop	h	; Calculate offset in array
lxi	d,-seq
jmp	prhl	; Print offset of pair whose GCD is not 1
done:	lxi	d,gcdy	; Print OK message
mvi	c,puts
jmp	5
;;;	GCD(A,B)
gcd:	cmp	b
rz		; If A=B, result = A
jc	b_le_a	; B>A?
sub	b	; If A>B, subtract B
jmp 	gcd	; and loop
b_le_a:	mov	c,a
mov	a,b
sub	c
mov	b,a
mov	a,c
jmp	gcd
;;;	Print indices of occurrences of C numbers
;;;	starting at B
fnext:	lxi	d,seq
fsrch:	ldax	d	; Get current member
cmp	b	; Is it the number we are looking for?
inx	d	; Increment number
jnz	fsrch	; If no match, check next number
lxi	h,-seq	; Match - subtract start of array
call	prhl	; Print index
inr	b	; Look for next number
dcr	c	; If we need more numbers
jnz	fnext
push	d	; Save sequence pointer
lxi	d,nl	; Print newline
mvi	c,puts
call	5
pop	d	; Restore sequence pointer
ret
;;;	Print HL as ASCII number.
prhl:	push	h	; Save all registers
push	d
push	b
lxi	b,pnum	; Store pointer to num string on stack
push	b
lxi	b,-10	; Divisor
prdgt:	lxi	d,-1
prdgtl:	inx	d	; Divide by 10 through trial subtraction
jc	prdgtl
mvi	a,'0'+10
add	l	; L = remainder - 10
pop	h	; Get pointer from stack
dcx	h	; Store digit
mov	m,a
push	h	; Put pointer back on stack
xchg		; Put quotient in HL
mov	a,h	; Check if zero
ora	l
jnz	prdgt	; If not, next digit
pop	d	; Get pointer and put in DE
mvi	c,9	; CP/M print string
call	5
pop	b	; Restore registers
pop	d
pop	h
ret
db	'*****'	; Placeholder for number
pnum:	db	' \$'
nl:	db	13,10,'\$'
gcdn:	db	'GCD not 1 at: \$'
gcdy:	db	'GCD of all pairs of consecutive members is 1.\$'
seq:	db	1,1	; Sequence stored here```
Output:
```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
GCD of all pairs of consecutive members is 1.```

8086 Assembly

```puts:	equ	9
cpu	8086
bits	16
org	100h
section	.text
;;;	Generate the first 1200 elemets of the Stern-Brocot sequence
mov	cx,600	; 2 elements generated per loop
mov	si,seq
mov	di,seq+2
lodsb
mov	ah,al	; AH = predecessor
genseq:	lodsb		; AL = considered member
add	ah,al	; AH = sum
xchg	ah,al	; Swap them (AL = sum, AH = member)
stosw		; Write sum and current considered member
loop	genseq	; Loop 600 times
;;;	Print first 15 members of sequence
mov	si,seq
mov	cx,15
p15:	lodsb		; Get member
cbw
call	prax 	; Print member
loop	p15
call	prnl
;;;	Print first occurrences of [1..10]
mov	al,1
mov	cx,10
call	find
call	prnl
;;;	Print first occurrence of 100
mov	al,100
mov	cx,1
call	find
call	prnl
;;;	Check pairs of GCDs
mov	cx,1000	; 1000 times
mov	si,seq
lodsb
gcdchk:	mov	ah,al	; AH = last member, AL = current member
lodsb
mov	dx,ax	; Calculate GCD
call	gcd
dec	dl	; See if it is 1
jnz	.fail	; If not, failure
loop	gcdchk	; Otherwise, check next pair
mov	dx,gcdy	; GCD of all pairs is 0
jmp	pstr
.fail:	mov	dx,gcdn	; GCD of current pair is not 0
call	pstr
mov	ax,si
sub	ax,seq+1
jmp	prax
;;;	DL = gcd(DL,DH)
gcd:	cmp	dl,dh
jl	.lt	; DL < DH
jg	.gt	; DL > DH
ret
.lt:	sub	dh,dl	; DL < DH
jmp	gcd
.gt: 	sub	dl,dh	; DL > DH
jmp	gcd
;;;	Print indices of CX consecutive numbers starting
;;;	at AL.
find:	mov	di,seq
push	cx	; Keep loop counter
mov	cx,-1
repne	scasb	; Find AL starting at [DI]
pop	cx	; Restore loop counter
xchg	si,ax	; Keep AL in SI
mov	ax,di	; Calculate index in sequence
sub	ax,seq
call	prax	; Output
xchg	si,ax	; Restore AL
inc	ax	; Increment
loop 	find	; Keep going CX times
ret
;;;	Print newline
prnl:	mov	dx,nl
jmp	pstr
;;;	Print number in AX
;;;	Destroys AX, BX, DX, BP
prax:	mov	bp,10	; Divisor
mov	bx,numbuf
.loop:	xor	dx,dx	; DX = 0
div	bp	; Divide DX:AX by 10; DX = remainder
dec	bx	; Move string pointer back
add	dl,'0'	; Make ASCII digit
mov	[bx],dl	; Write digit
test	ax,ax	; Any digits left?
jnz	.loop
mov	dx,bx
pstr:	mov	ah,puts	; Print number string
int	21h
ret
section	.data
gcdn:	db	'GCD not 1 at: \$'
gcdy:	db	'GCD of all pairs of consecutive members is 1.\$'
db	'*****'
numbuf:	db	' \$'
nl:	db	13,10,'\$'
seq:	db	1,1
```
Output:
```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
GCD of all pairs of consecutive members is 1.```

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```
Output:
```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
```

```with Ada.Text_IO, Ada.Containers.Vectors;

procedure Sequence is

package Vectors is new
Ada.Containers.Vectors(Index_Type => Positive, Element_Type => Positive);
use type Vectors.Vector;

type Sequence is record
List: Vectors.Vector;
Index: Positive;
-- This implements some form of "lazy evaluation":
--  + List holds the elements computed, so far, it is extended
--    if the user tries to "Get" an element not yet computed;
--  + Index is the location of the next element under consideration
end record;

function Initialize return Sequence is
(List => (Vectors.Empty_Vector & 1 & 1), Index => 2);

function Get(Seq: in out Sequence; Location: Positive) return Positive is
-- returns the Location'th element of the sequence
-- extends Seq.List (and then increases Seq.Index) if neccessary
That: Positive := Seq.List.Element(Seq.Index);
This: Positive := That + Seq.List.Element(Seq.Index-1);
begin
while Seq.List.Last_Index < Location loop
Seq.List := Seq.List & This & That;
Seq.Index := Seq.Index + 1;
end loop;
return Seq.List.Element(Location);
end Get;

S: Sequence := Initialize;
J: Positive;

begin
-- show first fifteen members
Put("First 15:");
for I in 1 .. 15 loop
Put(Integer'Image(Get(S, I)));
end loop;
New_Line;

-- show the index where 1, 2, 3, ... first appear in the sequence
for I in 1 .. 10 loop
J := 1;
while Get(S, J) /= I loop
J := J + 1;
end loop;
Put("First" & Integer'Image(I) & " at" & Integer'Image(J) & ";  ");
if I mod 4 = 0 then
New_Line; -- otherwise, the output gets a bit too ugly
end if;
end loop;

-- show the index where 100 first appears in the sequence
J := 1;
while Get(S, J) /= 100 loop
J := J + 1;
end loop;
Put_Line("First 100 at" & Integer'Image(J) & ".");

-- check GCDs
declare
function GCD (A, B : Integer) return Integer is
M : Integer := A;
N : Integer := B;
T : Integer;
begin
while N /= 0 loop
T := M;
M := N;
N := T mod N;
end loop;
return M;
end GCD;

A, B: Positive;
begin
for I in 1 .. 999 loop
A := Get(S, I);
B := Get(S, I+1);
if GCD(A, B) /= 1 then
raise Constraint_Error;
end if;
end loop;
Put_Line("Correct: The first 999 consecutive pairs are relative prime!");
exception
when Constraint_Error => Put_Line("Some GCD > 1; this is wrong!!!") ;
end;
end Sequence;
```
Output:
```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.
Correct: The first 999 consecutive pairs are relative prime!```

ALGOL 68

```BEGIN # find members of the Stern-Brocot sequence: starting from 1, 1 the     #
# subsequent members are the previous two members summed followed by    #
# the previous                                                          #
# 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 Stern-Brocot sequence up to n                   #
OP   STERNBROCOT = ( INT n )[]INT:
BEGIN
[ 1 : IF ODD n THEN n + 1 ELSE n FI ]INT result;
IF n > 0 THEN
result[ 1 ]  := result[ 2 ] := 1;
INT next pos := 2;
FOR i FROM 3 WHILE next pos < n DO
INT p1 = result[ i - 1 ];
result[ next pos +:= 1 ] := p1 + result[ i - 2 ];
result[ next pos +:= 1 ] := p1
OD
FI;
result[ 1 : n ]
END # STERNPROCOT # ;
FLEX[ 1 : 0 ]INT sb := STERNBROCOT 1000; # start with 1000 elements        #
# if that isn't enough, more will be added later #
# show the first 15 elements of the sequence                               #
print( ( "The first 15 elements of the Stern-Brocot sequence are:", newline ) );
FOR i TO 15 DO
print( ( whole( sb[ i ], -3 ) ) )
OD;
print( ( newline, newline ) );
# find where the numbers 1-10 first appear                                 #
INT found 10 := 0;
[ 10 ]INT pos 10; FOR i TO UPB pos 10 DO pos 10[ i ] := 0 OD;
FOR i TO UPB sb WHILE found 10 < 10 DO
INT sb i = sb[ i ];
IF sb i <= UPB pos 10 THEN
IF pos 10[ sb i ] = 0 THEN
# first occurance of this number                               #
pos 10[ sb i ] := i;
found 10      +:= 1
FI
FI
OD;
print( ( "The first positions of 1..", whole( UPB pos 10, 0 ), " in the sequence are:", newline ) );
FOR i TO UPB pos 10 DO
print( ( whole( i, -2 ), ":", whole( pos 10[ i ], 0 ), " " ) )
OD;
print( ( newline, newline ) );
# find where the number 100 first appears                                  #
BOOL found 100 := FALSE;
IF i > UPB sb THEN
# need more elements                                               #
sb := STERNBROCOT ( UPB sb * 2 )
FI;
IF sb[ i ] = 100 THEN
print( ( "100 first appears at position ", whole( i, 0 ), newline, newline ) );
found 100 := TRUE
FI
OD;
# check that the pairs of elements up to 1000 are coprime                  #
BOOL all coprime := TRUE;
FOR i FROM 2 TO 1000 WHILE all coprime DO
all coprime := gcd( sb[ i ], sb[ i - 1 ] ) = 1
OD;
print( ( "Element pairs up to 1000 are ", IF all coprime THEN "" ELSE "NOT " FI, "coprime", newline ) )
END```
Output:
```The first 15 elements of the Stern-Brocot sequence are:
1  1  2  1  3  2  3  1  4  3  5  2  5  3  4

The first positions of 1..10 in the sequence are:
1:1  2:3  3:5  4:9  5:11  6:33  7:19  8:21  9:35 10:39

100 first appears at position 1179

Element pairs up to 1000 are coprime```

ALGOL-M

```begin
integer array S[1:1200];
integer i,ok;

integer function gcd(a,b);
integer a,b;
gcd :=
if a>b then gcd(a-b,b)
else if a<b then gcd(a,b-a)
else a;

integer function first(n);
integer n;
begin
integer i;
i := 1;
while S[i]<>n do i := i + 1;
first := i;
end;

S[1] := S[2] := 1;
for i := 2 step 1 until 600 do
begin
S[i*2-1] := S[i] + S[i-1];
S[i*2] := S[i];
end;

write("First 15 numbers:");
for i := 1 step 1 until 15 do
begin
if i-i/5*5=1 then write(S[i]) else writeon(S[i]);
end;

write("");
write("First occurrence:");
for i := 1 step 1 until 10 do write(i, " at", first(i));
write(100, " at", first(100));

ok := 1;
for i := 1 step 1 until 999 do
begin
if gcd(S[i], S[i+1]) <> 1 then
begin
write("gcd",S[i],",",S[i+1],"<> 1");
ok := 0;
end;
end;
if ok = 1 then write("The GCD of each pair of consecutive members is 1.");
end```
Output:
```First 15 numbers:
1     1     2     1     3
2     3     1     4     3
5     2     5     3     4

First occurrence:
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
The GCD of each pair of consecutive members is 1.```

Amazing Hopper

Version: hopper-FLOW!:

```#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```
Output:
```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
```

APL

```task←{
stern←{⍵{
⍺←0 ⋄ ⍺⍺≤⍴⍵:⍺⍺↑⍵
(⍺+1)∇⍵,(+/,2⊃⊣)2↑⍺↓⍵
}1 1}
seq←stern 1200 ⍝ Cache 1200 elements
⎕←'First 15 elements:',15↑seq
⎕←'Locations of 1..10:',seq⍳⍳10
⎕←'Location of 100:',seq⍳100
⎕←'All GCDs 1:','no' 'yes'[1+1∧.=2∨/1000↑seq]
}
```
Output:
```First 15 elements: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
Locations of 1..10: 1 3 5 9 11 33 19 21 35 39
Location of 100: 1179
All GCDs 1: yes ```

AppleScript

```use AppleScript version "2.4"
use framework "Foundation"

------------------ STERN-BROCOT SEQUENCE -----------------

-- sternBrocot :: Generator [Int]
on sternBrocot()
script go
on |λ|(xs)
set x to snd(xs)
tail(xs) & {fst(xs) + x, x}
end |λ|
end script
end sternBrocot

--------------------------- TEST -------------------------
on run
set sbs to take(1200, sternBrocot())
set ixSB to zip(sbs, enumFrom(1))

script low
on |λ|(x)
12 ≠ fst(x)
end |λ|
end script

script sameFst
on |λ|(a, b)
fst(a) = fst(b)
end |λ|
end script

script asList
on |λ|(x)
{fst(x), snd(x)}
end |λ|
end script

script below100
on |λ|(x)
100 ≠ fst(x)
end |λ|
end script

script fullyReduced
on |λ|(ab)
1 = gcd(|1| of ab, |2| of ab)
end |λ|
end script

unlines(map(showJSON, ¬
{take(15, sbs), ¬
take(10, map(asList, ¬
nubBy(sameFst, ¬
sortBy(comparing(fst), ¬
takeWhile(low, ixSB))))), ¬
asList's |λ|(fst(take(1, dropWhile(below100, ixSB)))), ¬
all(fullyReduced, take(1000, zip(sbs, tail(sbs))))}))
end run

--> [1,1,2,1,3,2,3,1,4,3,5,2,5,3,4]
--> [[1,32],[2,24],[3,40],[4,36],[5,44],[6,33],[7,38],[8,42],[9,35],[10,39]]
--> [100,1179]
--> true

------------------------- GENERIC ------------------------

-- Absolute value.
-- abs :: Num -> Num
on abs(x)
if 0 > x then
-x
else
x
end if
end abs

-- Applied to a predicate and a list, `all` determines if all elements
-- of the list satisfy the predicate.
-- all :: (a -> Bool) -> [a] -> Bool
on all(p, xs)
tell mReturn(p)
set lng to length of xs
repeat with i from 1 to lng
if not |λ|(item i of xs, i, xs) then return false
end repeat
true
end tell
end all

-- comparing :: (a -> b) -> (a -> a -> Ordering)
on comparing(f)
script
on |λ|(a, b)
tell mReturn(f)
set fa to |λ|(a)
set fb to |λ|(b)
if fa < fb then
-1
else if fa > fb then
1
else
0
end if
end tell
end |λ|
end script
end comparing

-- drop :: Int -> [a] -> [a]
-- drop :: Int -> String -> String
on drop(n, xs)
set c to class of xs
if c is not script then
if c is not string then
if n < length of xs then
items (1 + n) thru -1 of xs
else
{}
end if
else
if n < length of xs then
text (1 + n) thru -1 of xs
else
""
end if
end if
else
take(n, xs) -- consumed
return xs
end if
end drop

-- dropWhile :: (a -> Bool) -> [a] -> [a]
-- dropWhile :: (Char -> Bool) -> String -> String
on dropWhile(p, xs)
set lng to length of xs
set i to 1
tell mReturn(p)
repeat while i ≤ lng and |λ|(item i of xs)
set i to i + 1
end repeat
end tell
drop(i - 1, xs)
end dropWhile

-- enumFrom :: a -> [a]
on enumFrom(x)
script
property v : missing value
property blnNum : class of x is not text
on |λ|()
if missing value is not v then
if blnNum then
set v to 1 + v
else
set v to succ(v)
end if
else
set v to x
end if
return v
end |λ|
end script
end enumFrom

-- filter :: (a -> Bool) -> [a] -> [a]
on filter(f, xs)
tell mReturn(f)
set lst to {}
set lng to length of xs
repeat with i from 1 to lng
set v to item i of xs
if |λ|(v, i, xs) then set end of lst to v
end repeat
return lst
end tell
end filter

-- fmapGen <\$> :: (a -> b) -> Gen [a] -> Gen [b]
on fmapGen(f, gen)
script
property g : gen
property mf : mReturn(f)'s |λ|
on |λ|()
set v to g's |λ|()
if v is missing value then
v
else
mf(v)
end if
end |λ|
end script
end fmapGen

-- fst :: (a, b) -> a
on fst(tpl)
if class of tpl is record then
|1| of tpl
else
item 1 of tpl
end if
end fst

-- gcd :: Int -> Int -> Int
on gcd(a, b)
set x to abs(a)
set y to abs(b)
repeat until y = 0
if x > y then
set x to x - y
else
set y to y - x
end if
end repeat
return x
end gcd

-- head :: [a] -> a
if xs = {} then
missing value
else
item 1 of xs
end if

-- iterate :: (a -> a) -> a -> Gen [a]
on iterate(f, x)
script
property v : missing value
property g : mReturn(f)'s |λ|
on |λ|()
if missing value is v then
set v to x
else
set v to g(v)
end if
return v
end |λ|
end script
end iterate

-- length :: [a] -> Int
on |length|(xs)
set c to class of xs
if list is c or string is c then
length of xs
else
(2 ^ 29 - 1) -- (maxInt - simple proxy for non-finite)
end if
end |length|

-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map

-- min :: Ord a => a -> a -> a
on min(x, y)
if y < x then
y
else
x
end if
end min

-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn

-- nubBy :: (a -> a -> Bool) -> [a] -> [a]
on nubBy(f, xs)
set g to mReturn(f)'s |λ|

script notEq
property fEq : g
on |λ|(a)
script
on |λ|(b)
not fEq(a, b)
end |λ|
end script
end |λ|
end script

script go
on |λ|(xs)
if (length of xs) > 1 then
set x to item 1 of xs
{x} & go's |λ|(filter(notEq's |λ|(x), items 2 thru -1 of xs))
else
xs
end if
end |λ|
end script

go's |λ|(xs)
end nubBy

-- partition :: predicate -> List -> (Matches, nonMatches)
-- partition :: (a -> Bool) -> [a] -> ([a], [a])
on partition(f, xs)
tell mReturn(f)
set ys to {}
set zs to {}
repeat with x in xs
set v to contents of x
if |λ|(v) then
set end of ys to v
else
set end of zs to v
end if
end repeat
end tell
Tuple(ys, zs)
end partition

-- showJSON :: a -> String
on showJSON(x)
set c to class of x
if (c is list) or (c is record) then
set ca to current application
set {json, e} to ca's NSJSONSerialization's dataWithJSONObject:x options:0 |error|:(reference)
if json is missing value then
e's localizedDescription() as text
else
(ca's NSString's alloc()'s initWithData:json encoding:(ca's NSUTF8StringEncoding)) as text
end if
else if c is date then
"\"" & ((x - (time to GMT)) as «class isot» as string) & ".000Z" & "\""
else if c is text then
"\"" & x & "\""
else if (c is integer or c is real) then
x as text
else if c is class then
"null"
else
try
x as text
on error
("«" & c as text) & "»"
end try
end if
end showJSON

-- snd :: (a, b) -> b
on snd(tpl)
if class of tpl is record then
|2| of tpl
else
item 2 of tpl
end if
end snd

-- Enough for small scale sorts.
-- Use instead sortOn :: Ord b => (a -> b) -> [a] -> [a]
-- which is equivalent to the more flexible sortBy(comparing(f), xs)
-- and uses a much faster ObjC NSArray sort method
-- sortBy :: (a -> a -> Ordering) -> [a] -> [a]
on sortBy(f, xs)
if length of xs > 1 then
set h to item 1 of xs
set f to mReturn(f)
script
on |λ|(x)
f's |λ|(x, h) ≤ 0
end |λ|
end script
set lessMore to partition(result, rest of xs)
sortBy(f, |1| of lessMore) & {h} & ¬
sortBy(f, |2| of lessMore)
else
xs
end if
end sortBy

-- tail :: [a] -> [a]
on tail(xs)
set blnText to text is class of xs
if blnText then
set unit to ""
else
set unit to {}
end if
set lng to length of xs
if 1 > lng then
missing value
else if 2 > lng then
unit
else
if blnText then
text 2 thru -1 of xs
else
rest of xs
end if
end if
end tail

-- take :: Int -> [a] -> [a]
-- take :: Int -> String -> String
on take(n, xs)
set c to class of xs
if list is c then
if 0 < n then
items 1 thru min(n, length of xs) of xs
else
{}
end if
else if string is c then
if 0 < n then
text 1 thru min(n, length of xs) of xs
else
""
end if
else if script is c then
set ys to {}
repeat with i from 1 to n
set v to xs's |λ|()
if missing value is v then
return ys
else
set end of ys to v
end if
end repeat
return ys
else
missing value
end if
end take

-- takeWhile :: (a -> Bool) -> [a] -> [a]
-- takeWhile :: (Char -> Bool) -> String -> String
on takeWhile(p, xs)
if script is class of xs then
takeWhileGen(p, xs)
else
tell mReturn(p)
repeat with i from 1 to length of xs
if not |λ|(item i of xs) then ¬
return take(i - 1, xs)
end repeat
end tell
return xs
end if
end takeWhile

-- takeWhileGen :: (a -> Bool) -> Gen [a] -> [a]
on takeWhileGen(p, xs)
set ys to {}
set v to |λ|() of xs
tell mReturn(p)
repeat while (|λ|(v))
set end of ys to v
set v to xs's |λ|()
end repeat
end tell
return ys
end takeWhileGen

-- Tuple (,) :: a -> b -> (a, b)
on Tuple(a, b)
{type:"Tuple", |1|:a, |2|:b, length:2}
end Tuple

-- unlines :: [String] -> String
on unlines(xs)
set {dlm, my text item delimiters} to ¬
{my text item delimiters, linefeed}
set str to xs as text
set my text item delimiters to dlm
str
end unlines

-- zip :: [a] -> [b] -> [(a, b)]
on zip(xs, ys)
zipWith(Tuple, xs, ys)
end zip

-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
on zipWith(f, xs, ys)
set lng to min(|length|(xs), |length|(ys))
if 1 > lng then return {}
set xs_ to take(lng, xs) -- Allow for non-finite
set ys_ to take(lng, ys) -- generators like cycle etc
set lst to {}
tell mReturn(f)
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs_, item i of ys_)
end repeat
return lst
end tell
end zipWith
```
Output:
```[1,1,2,1,3,2,3,1,4,3,5,2,5,3,4]
[[1,32],[2,24],[3,40],[4,36],[5,44],[6,33],[7,38],[8,42],[9,35],[10,39]]
[100,1179]
true```

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."
```
Output:
```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.```

AutoHotkey

```Found := FindOneToX(100), FoundList := ""
Loop, 10
FoundList .= "First " A_Index " found at " Found[A_Index] "`n"
MsgBox, 64, Stern-Brocot Sequence
, % "First 15: " FirstX(15) "`n"
.    FoundList
.   "First 100 found at " Found[100] "`n"
.   "GCDs of all two consecutive members are " (GCDsUpToXAreOne(1000) ? "" : "not ") "one."
return

class SternBrocot
{
__New()
{
this[1] := 1
this[2] := 1
this.Consider := 2
}

InsertPair()
{
n := this.Consider
this.Push(this[n] + this[n - 1], this[n])
this.Consider++
}
}

; 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)
FirstX(x)
{
SB := new SternBrocot()
while SB.MaxIndex() < x
SB.InsertPair()
Loop, % x
Out .= SB[A_Index] ", "
return RTrim(Out, " ,")
}

; Show the (1-based) index of where the numbers 1-to-10 first appears in the sequence.
; Show the (1-based) index of where the number 100 first appears in the sequence.
FindOneToX(x)
{
SB := new SternBrocot(), xRequired := x, Found := []
while xRequired > 0                     ; While the count of numbers yet to be found is > 0.
{
Loop, 2                      ; Consider the second last member and then the last member.
{
n := SB[i := SB.MaxIndex() - 2 + A_Index]
; If number (n) has not been found yet, and it is less than the maximum number to
; find (x), record the index (i) and decrement the count of numbers yet to be found.
if (Found[n] = "" && n <= x)
Found[n] := i, xRequired--
}
SB.InsertPair()                      ; Insert the two members that will be checked next.
}
return Found
}

; Check that the greatest common divisor of all the two consecutive members of the series up to
; the 1000th member, is always one.
GCDsUpToXAreOne(x)
{
SB := new SternBrocot()
while SB.MaxIndex() < x
SB.InsertPair()
Loop, % x - 1
if GCD(SB[A_Index], SB[A_Index + 1]) > 1
return 0
return 1
}

GCD(a, b) {
while b
b := Mod(a | 0x0, a := b)
return a
}
```
Output:
```First 15: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4
First 1 found at 1
First 2 found at 3
First 3 found at 5
First 4 found at 9
First 5 found at 11
First 6 found at 33
First 7 found at 19
First 8 found at 21
First 9 found at 35
First 10 found at 39
First 100 found at 1179
GCDs of all two consecutive members are one.```

BASIC

```10 DEFINT A,B,I,J,S: DIM S(1200)
20 S(1)=1: S(2)=1
30 FOR I=2 TO 600
40 S(I*2-1)=S(I)+S(I-1)
50 S(I*2)=S(I)
60 NEXT I
70 PRINT "First 15 elements: ";
80 FOR I=1 TO 15: PRINT USING"# ";S(I);: NEXT I
85 PRINT
90 FOR I=1 TO 10
100 FOR J=1 TO 1200: IF S(J)<>I THEN NEXT J
110 PRINT "First";I;"at";J
120 NEXT I
130 FOR J=1 TO 1200: IF S(J)<>100 THEN NEXT J
140 PRINT "First 100 at";J
150 FOR I=2 TO 1000
160 A=S(I): B=S(I-1)
170 J=A: A=B: B=J MOD A: IF B THEN 170
180 IF A<>1 THEN PRINT "GCD <> 1 at ";I: STOP
190 NEXT I
200 PRINT "All GCDs are 1."
210 END
```
Output:
```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 are 1.
```

BASIC256

Translation of: FreeBASIC
```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```
Output:
`Igual que la entrada de FreeBASIC.`

QBasic

Translation of: FreeBASIC
Works with: QBasic version 1.1
```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
```
Output:
`Igual que la entrada de FreeBASIC.`

Yabasic

Translation of: FreeBASIC
```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```
Output:
`Igual que la entrada de FreeBASIC.`

BCPL

```get "libhdr"

manifest \$( AMOUNT = 1200 \$)

let gcd(a,b) =
a>b -> gcd(a-b, b),
a<b -> gcd(a, b-a),
a

let mkstern(s, n) be
\$(  s!1 := 1
s!2 := 1
for i=2 to n/2 do
\$(  s!(i*2-1) := s!i + s!(i-1)
s!(i*2) := s!i
\$)
\$)

let find(v, n, max) = valof
for i=1 to max
if v!i=n then resultis i

let findwrite(v, n, max) be
writef("%I3 at %I4*N", n, find(v, n, max))

let start() be
\$(  let stern = vec AMOUNT
mkstern(stern, AMOUNT)

writes("First 15 numbers: ")
for i=1 to 15 do writef("%N ", stern!i)

writes("*N*NFirst occurrence:*N")
for i=1 to 10 do findwrite(stern, i, AMOUNT)
findwrite(stern, 100, AMOUNT)

if valof
\$(  for i=2 to AMOUNT
unless gcd(stern!i, stern!(i-1)) = 1
resultis false
resultis true
\$) then
writes("*NThe GCD of each pair of consecutive members is 1.*N")
\$)```
Output:
```First 15 numbers: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4

First occurrence:
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

The GCD of each pair of consecutive members is 1.```

C

Recursive function.

```#include <stdio.h>

typedef unsigned int uint;

/* the sequence, 0-th member is 0 */
uint f(uint n)
{
return n < 2 ? n : (n&1) ? f(n/2) + f(n/2 + 1) : f(n/2);
}

uint gcd(uint a, uint b)
{
return a ? a < b ? gcd(b%a, a) : gcd(a%b, b) : b;
}

void find(uint from, uint to)
{
do {
uint n;
for (n = 1; f(n) != from ; n++);
printf("%3u at Stern #%u.\n", from, n);
} while (++from <= to);
}

int main(void)
{
uint n;
for (n = 1; n < 16; n++) printf("%u ", f(n));
puts("are the first fifteen.");

find(1, 10);
find(100, 0);

for (n = 1; n < 1000 && gcd(f(n), f(n+1)) == 1; n++);
printf(n == 1000 ? "All GCDs are 1.\n" : "GCD of #%d and #%d is not 1", n, n+1);

return 0;
}
```
Output:
```1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 are the first fifteen.
1 at Stern #1.
2 at Stern #3.
3 at Stern #5.
4 at Stern #9.
5 at Stern #11.
6 at Stern #33.
7 at Stern #19.
8 at Stern #21.
9 at Stern #35.
10 at Stern #39.
100 at Stern #1179.
All GCDs are 1.
```

The above `f()` can be replaced by the following, which is much faster but probably less obvious as to how it arrives from the recurrence relations.

```uint f(uint n)
{
uint a = 1, b = 0;
while (n) {
if (n&1) b += a;
else	 a += b;
n >>= 1;
}
return b;
}
```

C#

```using System;
using System.Collections.Generic;
using System.Linq;

static class Program {
static List<int> l = new List<int>() { 1, 1 };

static int gcd(int a, int b) {
return a > 0 ? a < b ? gcd(b % a, a) : gcd(a % b, b) : b; }

static void Main(string[] args) {
int max = 1000; int take = 15; int i = 1;
int[] selection = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100 };
do { l.AddRange(new List<int>() { l[i] + l[i - 1], l[i] }); i += 1; }
while (l.Count < max || l[l.Count - 2] != selection.Last());
Console.Write("The first {0} items In the Stern-Brocot sequence: ", take);
Console.WriteLine("{0}\n", string.Join(", ", l.Take(take)));
Console.WriteLine("The locations of where the selected numbers (1-to-10, & 100) first appear:");
foreach (int ii in selection) {
int j = l.FindIndex(x => x == ii) + 1; Console.WriteLine("{0,3}: {1:n0}", ii, j); }
Console.WriteLine(); bool good = true;
for (i = 1; i <= max; i++) { if (gcd(l[i], l[i - 1]) != 1) { good = false; break; } }
Console.WriteLine("The greatest common divisor of all the two consecutive items of the" +
" series up to the {0}th item is {1}always one.", max, good ? "" : "not ");
}
}
```
Output:
```The first 15 items In the Stern-Brocot sequence: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4

The locations of where the selected numbers (1-to-10, & 100) first appear:
1: 1
2: 3
3: 5
4: 9
5: 11
6: 33
7: 19
8: 21
9: 35
10: 39
100: 1,179

The greatest common divisor of all the two consecutive items of the series up to the 1000th item is always one.
```

C++

```#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>

unsigned gcd( unsigned i, unsigned j ) {
return i ? i < j ? gcd( j % i, i ) : gcd( i % j, j ) : j;
}
void createSequence( std::vector<unsigned>& seq, int c ) {
if( 1500 == seq.size() ) return;
unsigned t = seq.at( c ) + seq.at( c + 1 );
seq.push_back( t );
seq.push_back( seq.at( c + 1 ) );
createSequence( seq, c + 1 );
}
int main( int argc, char* argv[] ) {
std::vector<unsigned> seq( 2, 1 );
createSequence( seq, 0 );

std::cout << "First fifteen members of the sequence:\n    ";
for( unsigned x = 0; x < 15; x++ ) {
std::cout << seq[x] << " ";
}

std::cout << "\n\n";
for( unsigned x = 1; x < 11; x++ ) {
std::vector<unsigned>::iterator i = std::find( seq.begin(), seq.end(), x );
if( i != seq.end() ) {
std::cout << std::setw( 3 ) << x << " is at pos. #" << 1 + distance( seq.begin(), i ) << "\n";
}
}

std::cout << "\n";
std::vector<unsigned>::iterator i = std::find( seq.begin(), seq.end(), 100 );
if( i != seq.end() ) {
std::cout << 100 << " is at pos. #" << 1 + distance( seq.begin(), i ) << "\n";
}

std::cout << "\n";
unsigned g;
bool f = false;
for( int x = 0, y = 1; x < 1000; x++, y++ ) {
g =  gcd( seq[x], seq[y] );
if( g != 1 ) f = true;
std::cout << std::setw( 4 ) << x + 1 << ": GCD (" << seq[x] << ", "
<< seq[y] << ") = " << g << ( g != 1 ? " <-- ERROR\n" : "\n" );
}
std::cout << "\n" << ( f ? "THERE WERE ERRORS --- NOT ALL GCDs ARE '1'!" : "CORRECT: ALL GCDs ARE '1'!" ) << "\n\n";
return 0;
}
```
Output:
```First fifteen members of the sequence:
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4

1 is at pos. #1
2 is at pos. #3
3 is at pos. #5
4 is at pos. #9
5 is at pos. #11
6 is at pos. #33
7 is at pos. #19
8 is at pos. #21
9 is at pos. #35
10 is at pos. #39

100 is at pos. #1179

1: GCD (1, 1) = 1
2: GCD (1, 2) = 1
3: GCD (2, 1) = 1
4: GCD (1, 3) = 1
5: GCD (3, 2) = 1
6: GCD (2, 3) = 1
7: GCD (3, 1) = 1
8: GCD (1, 4) = 1

[...]

993: GCD (26, 21) = 1
994: GCD (21, 37) = 1
995: GCD (37, 16) = 1
996: GCD (16, 43) = 1
997: GCD (43, 27) = 1
998: GCD (27, 38) = 1
999: GCD (38, 11) = 1
1000: GCD (11, 39) = 1

CORRECT: ALL GCDs ARE '1'!
```

Clojure

```;; each step adds two items
(defn sb-step [v]
(let [i (quot (count v) 2)]
(conj v (+ (v (dec i)) (v i)) (v i))))

;; A lazy, infinite sequence -- `take` what you want.
(def all-sbs (sequence (map peek) (iterate sb-step [1 1])))

;; zero-based
(defn first-appearance [n]
(first (keep-indexed (fn [i x] (when (= x n) i)) all-sbs)))

;; inlined abs; rem is slightly faster than mod, and the same result for positive values
(defn gcd [a b]
(loop [a (if (neg? a) (- a) a)
b (if (neg? b) (- b) b)]
(if (zero? b)
a
(recur b (rem a b)))))

(defn check-pairwise-gcd [cnt]
(let [sbs (take (inc cnt) all-sbs)]
(every? #(= 1 %) (map gcd sbs (rest sbs)))))

;; one-based index required by problem statement
(defn report-sb []
(println "First 15 Stern-Brocot members:" (take 15 all-sbs))
(println "First appearance of N at 1-based index:")
(doseq [n [1 2 3 4 5 6 7 8 9 10 100]]
(println " first" n "at" (inc (first-appearance n))))
(println "Check pairwise GCDs = 1 ..." (check-pairwise-gcd 1000))
true)

(report-sb)
```
Output:
```First 15 Stern-Brocot members: (1 1 2 1 3 2 3 1 4 3 5 2 5 3 4)
First appearance of N at 1-based index:
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
Check pairwise GCDs = 1 ... true
true```

Clojure: Using Lazy Sequences

```(ns test-p.core)
(defn gcd
"(gcd a b) computes the greatest common divisor of a and b."
[a b]
(if (zero? b)
a
(recur b (mod a b))))

(defn stern-brocat-next [p]
" p is the block of the sequence we are using to compute the next block
This routine computes the next block "
(into [] (concat (rest p) [(+ (first p) (second p))] [(second p)])))

(defn seq-stern-brocat
([] (seq-stern-brocat [1 1]))
([p] (lazy-seq (cons (first p)
(seq-stern-brocat (stern-brocat-next p))))))

; First 15 elements
(println (take 15 (seq-stern-brocat)))

; Where numbers 1 to 10 first appear
(doseq [n (concat (range 1 11) [100])]
(println "The first appearnce of" n "is at index" (some (fn [[i k]] (when (= k n) (inc i)))
(map-indexed vector (seq-stern-brocat)))))

;; Check that gcd between 1st 1000 consecutive elements equals 1
;   Create cosecutive pairs of 1st 1000 elements
(def one-thousand-pairs (take 1000 (partition 2 1 (seq-stern-brocat))))
;   Check every pair has a gcd = 1
(println (every? (fn [[ith ith-plus-1]] (= (gcd ith ith-plus-1) 1))
one-thousand-pairs))
```
Output:
```(1 1 2 1 3 2 3 1 4 3 5 2 5 3 4)
The first appearnce of 1 is at index 1
The first appearnce of 2 is at index 3
The first appearnce of 3 is at index 5
The first appearnce of 4 is at index 9
The first appearnce of 5 is at index 11
The first appearnce of 6 is at index 33
The first appearnce of 7 is at index 19
The first appearnce of 8 is at index 21
The first appearnce of 9 is at index 35
The first appearnce of 10 is at index 39
The first appearnce of 100 is at index 1179
true
```

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```
Output:
```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.```

Common Lisp

```(defun stern-brocot (numbers)
(declare ((or null (vector integer)) numbers))
(cond ((null numbers)
(setf numbers (make-array 2 :element-type 'integer :adjustable t :fill-pointer t
:initial-element 1)))
((zerop (length numbers))
(vector-push-extend 1 numbers)
(vector-push-extend 1 numbers))
(t
(assert (evenp (length numbers)))
(let* ((considered-index (/ (length numbers) 2))
(considered (aref numbers considered-index))
(precedent  (aref numbers (1- considered-index))))
(vector-push-extend (+ considered precedent) numbers)
(vector-push-extend considered numbers))))
numbers)

(defun first-15 ()
(loop for input = nil then seq
for seq = (stern-brocot input)
while (< (length seq) 15)
finally (format t "First 15: ~{~A~^ ~}~%" (coerce (subseq seq 0 15) 'list))))

(defun first-1-to-10 ()
(loop with seq = (stern-brocot nil)
for i from 1 to 10
for index = (loop with start = 0
for pos = (position i seq :start start)
until pos
do (setf start (length seq)
seq   (stern-brocot seq))
finally (return (1+ pos)))
do (format t "First ~D at ~D~%" i index)))

(defun first-100 ()
(loop for input = nil then seq
for start = (length input)
for seq = (stern-brocot input)
for pos = (position 100 seq :start start)
until pos
finally (format t "First 100 at ~D~%" (1+ pos))))

(defun check-gcd ()
(loop for input = nil then seq
for seq = (stern-brocot input)
while (< (length seq) 1000)
finally (if (loop for i from 0 below 999
always (= 1 (gcd (aref seq i) (aref seq (1+ i)))))
(write-line "Correct.  The GCDs of all the two consecutive numbers are 1.")
(write-line "Wrong."))))

(defun main ()
(first-15)
(first-1-to-10)
(first-100)
(check-gcd))
```
Output:
```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
Correct.  The GCDs of all the two consecutive numbers are 1.```

Cowgol

```include "cowgol.coh";

# Redefining these is enough to change the type and length everywhere,
# but arrays are 0-based so you need one extra element.
typedef Stern is uint8;  # 8-bit math is enough for the numbers we need
var stern: Stern[1201];  # Array containing Stern-Brocot sequence

# Fill up the Stern-Brocot array
sub GenStern() is
stern[1] := 1;
stern[2] := 1;

var i: @indexof stern := 1;
var last: @indexof stern := @sizeof stern / 2;
while i <= last loop
stern[i*2-1] := stern[i] + stern[i-1];
stern[i*2] := stern[i];
i := i + 1;
end loop;
end sub;

# Find the first location of a given number
sub FindFirst(n: Stern): (i: @indexof stern) is
i := 1;
while i < @sizeof stern and stern[i] != n loop
i := i + 1;
end loop;
end sub;

GenStern(); # Generate sequence

# Print the first 15 numbers
var i: @indexof stern := 1;
while i <= 15 loop
print_i32(stern[i] as uint32);
print_char(' ');
i := i + 1;
end loop;
print_nl();

# Print the first occurrence of 1..10
var j: Stern := 1;
while j <= 10 loop
print_i32(FindFirst(j) as uint32);
print_char(' ');
j := j + 1;
end loop;
print_nl();

# Print the first occurrence of 100
print_i32(FindFirst(100) as uint32);
print_nl();

# Check that all GCDs of consecutive pairs are 1
sub gcd(a: Stern, b: Stern): (r: Stern) is
while a != b loop
if a > b then
a := a - b;
else
b := b - a;
end if;
end loop;
r := a;
end sub;

i := 1;
while i < @sizeof stern / 2 loop
if gcd(stern[i], stern[i+1]) != 1 then
print("GCD not 1 at: ");
print_i32(i as uint32);
print_nl();
ExitWithError();
end if;
i := i + 1;
end loop;

print("All GCDs are 1.\n");```
Output:
```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
All GCDs are 1.```

D

Translation of: Python
```import std.stdio, std.numeric, std.range, std.algorithm;

/// Generates members of the stern-brocot series, in order,
/// returning them when the predicate becomes false.
uint[] sternBrocot(bool delegate(in uint[]) pure nothrow @safe @nogc pred=seq => seq.length < 20)
pure nothrow @safe {
typeof(return) sb = [1, 1];
size_t i = 0;
while (pred(sb)) {
sb ~= [sb[i .. i + 2].sum, sb[i + 1]];
i++;
}
return sb;
}

void main() {
enum nFirst = 15;
writefln("The first %d values:\n%s\n", nFirst,
sternBrocot(seq => seq.length < nFirst).take(nFirst));

foreach (immutable nOccur; iota(1, 10 + 1).chain(100.only))
writefln("1-based index of the first occurrence of %3d in the series: %d",
nOccur, sternBrocot(seq => nOccur != seq[\$ - 2]).length - 1);

enum nGcd = 1_000;
auto s = sternBrocot(seq => seq.length < nGcd).take(nGcd);
assert(zip(s, s.dropOne).all!(ss => ss[].gcd == 1),
"A fraction from adjacent terms is reducible.");
}
```
Output:
```The first 15 values:
[1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]

1-based index of the first occurrence of   1 in the series: 1
1-based index of the first occurrence of   2 in the series: 3
1-based index of the first occurrence of   3 in the series: 5
1-based index of the first occurrence of   4 in the series: 9
1-based index of the first occurrence of   5 in the series: 11
1-based index of the first occurrence of   6 in the series: 33
1-based index of the first occurrence of   7 in the series: 19
1-based index of the first occurrence of   8 in the series: 21
1-based index of the first occurrence of   9 in the series: 35
1-based index of the first occurrence of  10 in the series: 39
1-based index of the first occurrence of 100 in the series: 1179```

This uses a queue from the Queue/usage Task:

```import std.stdio, std.algorithm, std.range, std.numeric, queue_usage2;

struct SternBrocot {
private auto sb = GrowableCircularQueue!uint(1, 1);
enum empty = false;
@property uint front() pure nothrow @safe @nogc {
return sb.front;
}
uint popFront() pure nothrow @safe {
sb.push(sb.front + sb[1]);
sb.push(sb[1]);
return sb.pop;
}
}

void main() {
SternBrocot().drop(50_000_000).front.writeln;
}
```
Output:
`7004`

Direct Version:

Translation of: C
```void main() {
import std.stdio, std.numeric, std.range, std.algorithm, std.bigint, std.conv;

/// Stern-Brocot sequence, 0-th member is 0.
T sternBrocot(T)(T n) pure nothrow /*safe*/ {
T a = 1, b = 0;
while (n) {
if (n & 1) b += a;
else       a += b;
n >>= 1;
}
return b;
}
alias sb = sternBrocot!uint;

enum nFirst = 15;
writefln("The first %d values:\n%s\n", nFirst, iota(1, nFirst + 1).map!sb);

foreach (immutable nOccur; iota(1, 10 + 1).chain(100.only))
writefln("1-based index of the first occurrence of %3d in the series: %d",
nOccur, sequence!q{n}.until!(n => sb(n) == nOccur).walkLength);

auto s = iota(1, 1_001).map!sb;
assert(s.zip(s.dropOne).all!(ss => ss[].gcd == 1),
"A fraction from adjacent terms is reducible.");

sternBrocot(10.BigInt ^^ 20_000).text.length.writeln;
}
```
Output:
```The first 15 values:
[1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]

1-based index of the first occurrence of   1 in the series: 1
1-based index of the first occurrence of   2 in the series: 3
1-based index of the first occurrence of   3 in the series: 5
1-based index of the first occurrence of   4 in the series: 9
1-based index of the first occurrence of   5 in the series: 11
1-based index of the first occurrence of   6 in the series: 33
1-based index of the first occurrence of   7 in the series: 19
1-based index of the first occurrence of   8 in the series: 21
1-based index of the first occurrence of   9 in the series: 35
1-based index of the first occurrence of  10 in the series: 39
1-based index of the first occurrence of 100 in the series: 1179
7984```

EasyLang

Translation of: Lua
```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)
.
for i to 1000
if gcd sb[i] sb[i + 1] <> 1
return "FAIL"
.
.
return "PASS"
.
sternbrocot 10000
for i to 15
write sb[i] & " "
.
for i to 10
print "\t" & i & " " & first i
.
print "\nTask 4: " & first 100
```
Output:
```Task 2: 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

```

EchoLisp

Function

```;; stern (2n ) = stern (n)
;; stern(2n+1) = stern(n) + stern(n+1)

(define (stern n)
(cond
(( < n 3) 1)
((even? n) (stern (/ n 2)))
(else (let ((m (/ (1- n) 2))) (+ (stern m) (stern (1+ m)))))))
(remember 'stern)
```
Output:
```; generate the sequence and check GCD
(for ((n 10000))
(unless (= (gcd (stern n) (stern (1+ n))) 1) (error "BAD GCD" n)))
→ #t

;; first items
(define sterns (cache 'stern))
(subvector sterns 1 16)
→ #( 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4)

;; first occurences index
(for ((i (in-range 1 11))) (write (vector-index i sterns)))
→  0 3 5 9 11 33 19 21 35 39

;; 100
(writeln (vector-index 100 sterns))
→ 1179

(stern 900000) → 446
(stern 900001) → 2479
```

Stream

From 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)))))
→ 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

;; computing f(1), f(f(1)), etc.
(define (f x)
(let [(a (/ (- (floor x) -1 (fract x))))]
(if (> a 1) (f a) (cons a a))))

(define T (make-stream f 1))
(for((i 19)) (write (stream-iterate T)))

→  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
```

Elixir

```defmodule SternBrocot do
def sequence do
Stream.unfold({0,{1,1}}, fn {i,acc} ->
a = elem(acc, i)
b = elem(acc, i+1)
{a, {i+1, Tuple.append(acc, a+b) |> Tuple.append(b)}}
end)
end

IO.write "First fifteen members of the sequence:\n  "
IO.inspect Enum.take(sequence, 15)
Enum.each(Enum.concat(1..10, [100]), fn n ->
i = Enum.find_index(sequence, &(&1==n)) + 1
IO.puts "#{n} first appears at #{i}"
end)
Enum.take(sequence, 1000)
|> Enum.chunk(2,1)
|> Enum.all?(fn [a,b] -> gcd(a,b) == 1 end)
|> if(do: "All GCD's are 1", else: "Whoops, not all GCD's are 1!")
|> IO.puts
end

defp gcd(a,0), do: abs(a)
defp gcd(a,b), do: gcd(b, rem(a,b))
end

```
Output:
```First fifteen members of the sequence:
[1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]
1 first appears at 1
2 first appears at 3
3 first appears at 5
4 first appears at 9
5 first appears at 11
6 first appears at 33
7 first appears at 19
8 first appears at 21
9 first appears at 35
10 first appears at 39
100 first appears at 1179
All GCD's are 1
```

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]
```

```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)
```
Output:
```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)
1179
There are 0 consecutive members, of the first thousand members, with GCD <> 1
```

Factor

Using the alternative function given in the C example for computing the Stern-Brocot sequence.

```USING: formatting io kernel lists lists.lazy locals math
math.ranges prettyprint sequences ;
IN: rosetta-code.stern-brocot

: fn ( n -- m )
[ 1 0 ] dip
[ dup zero? ] [
dup 1 bitand zero?
[ dupd [ + ] 2dip        ]
[ [ dup ] [ + ] [ ] tri* ] if
-1 shift
] until drop nip ;

:: search ( n -- m )
1 0 lfrom [ fn n = ] lfilter ltake list>array first ;

: first15 ( -- )
15 [1,b] [ fn pprint bl ] each
"are the first fifteen." print ;

: first-appearances ( -- )
10 [1,b] 100 suffix
[ dup search "First %3u at Stern #%u.\n" printf ] each ;

: gcd-test ( -- )
1,000 [1,b] [ dup 1 + [ fn ] bi@ gcd nip 1 = not ] filter
empty? "" " not" ? "All GCDs are%s 1.\n" printf ;

: main ( -- ) first15 first-appearances gcd-test ;

MAIN: main
```
Output:
```1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 are the first fifteen.
First   1 at Stern #1.
First   2 at Stern #3.
First   3 at Stern #5.
First   4 at Stern #9.
First   5 at Stern #11.
First   6 at Stern #33.
First   7 at Stern #19.
First   8 at Stern #21.
First   9 at Stern #35.
First  10 at Stern #39.
First 100 at Stern #1179.
All GCDs are 1.
```

Forth

```: stern ( n -- x : return N'th item of Stern-Brocot sequence)
dup 2 >= if
2 /mod swap if
dup 1+ recurse
swap recurse
+
else
recurse
then
then
;

: first ( n -- x : return X such that stern X = n )
1 begin over over stern <> while 1+ repeat
swap drop
;

: gcd ( a b -- a gcd b )
begin swap over mod dup 0= until drop
;

( Print first 15 numbers )
." First 15: " 1 begin dup stern . 1+ dup 15 > until
drop cr

( Print first occurrence of 1..10 )
1 begin
." First " dup . ." at " dup first .
1+ cr
dup 10 > until
drop

( Print first occurrence of 100 )
." First 100 at " 100 first . cr

( Check that the GCD of each adjacent pair up to 1000 is 1 )
-1 2 begin
dup stern over 1- stern gcd 1 =
rot and swap
1+
dup 1000 > until
swap if
." All GCDs are 1."
drop
else
." GCD <> 1 at: " .
then
cr
;

bye
```
Output:
```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
All GCDs are 1.
```

Fortran

Translation of: VBScript

Fortran IV

```* STERN-BROCOT SEQUENCE - FORTRAN IV
DIMENSION ISB(2400)
NN=2400
ISB(1)=1
ISB(2)=1
I=1
J=2
K=2
1    IF(K.GE.NN) GOTO 2
K=K+1
ISB(K)=ISB(K-I)+ISB(K-J)
K=K+1
ISB(K)=ISB(K-J)
I=I+1
J=J+1
GOTO 1
2    N=15
WRITE(*,101) N
101 FORMAT(1X,'FIRST',I4)
WRITE(*,102) (ISB(I),I=1,15)
102 FORMAT(15I4)
DO 5 J=1,11
JJ=J
IF(J.EQ.11) JJ=100
DO 3 I=1,K
IF(ISB(I).EQ.JJ) GOTO 4
3      CONTINUE
4      WRITE(*,103) JJ,I
103   FORMAT(1X,'FIRST',I4,' AT ',I4)
5    CONTINUE
END
```
Output:
```FIRST 15
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
```

Fortran 90

``` ! Stern-Brocot sequence - Fortran 90
parameter (nn=2400)
dimension isb(nn)
isb(1)=1; isb(2)=1
i=1; j=2; k=2
do while(k.lt.nn)
k=k+1; isb(k)=isb(k-i)+isb(k-j)
k=k+1; isb(k)=isb(k-j)
i=i+1; j=j+1
end do
n=15
write(*,"(1x,'First',i4)") n
write(*,"(15i4)") (isb(i),i=1,15)
do j=1,11
jj=j
if(j==11) jj=100
do i=1,k
if(isb(i)==jj) exit
end do
write(*,"(1x,'First',i4,' at ',i4)") jj,i
end do
end
```
Output:
``` 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
```

FreeBASIC

```' version 02-03-2019
' compile with: fbc -s console

#Define max 2000

Dim Shared As UInteger stern(max +2)

Sub stern_brocot

stern(1) = 1
stern(2) = 1

Dim As UInteger i = 2 , n = 2, ub = UBound(stern)

Do While i < ub
i += 1
stern(i) = stern(n) + stern(n -1)
i += 1
stern(i) = stern(n)
n += 1
Loop

End Sub

Function gcd(x As UInteger, y As UInteger) As UInteger

Dim As UInteger t

While y
t = y
y = x Mod y
x = t
Wend

Return x

End Function

' ------=< MAIN >=------

Dim As UInteger i

stern_brocot

Print "The first 15 are: " ;
For i = 1 To 15
Print stern(i); " ";
Next

Print : Print
Print "  Index   First nr."
Dim As UInteger d = 1
For i = 1 To max
If stern(i) = d Then
Print Using " ######"; i; stern(i)
d += 1
If d = 11 Then d = 100
If d = 101 Then Exit For
i = 0
End If
Next

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

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

' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
```
Output:
```The first 15 are: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4

Index   First nr.
1      1
3      2
5      3
9      4
11      5
33      6
19      7
21      8
35      9
39     10
1179    100

GCD of two consecutive members of the series up to the 1000th member is 1```

Go

```package main

import (
"fmt"

"sternbrocot"
)

func main() {
// Task 1, using the conventional sort of generator that generates
// terms endlessly.
g := sb.Generator()

// Task 2, demonstrating the generator.
fmt.Println("First 15:")
for i := 1; i <= 15; i++ {
fmt.Printf("%2d:  %d\n", i, g())
}

// Task 2 again, showing a simpler technique that might or might not be
// considered to "generate" terms.
s := sb.New()
fmt.Println("First 15:", s.FirstN(15))

for _, x := range []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100} {
fmt.Printf("%3d at 1-based index %d\n", x, 1+s.Find(x))
}

fmt.Println("1-based indexes: gcd")
for n, f := range s.FirstN(1000)[:999] {
g := gcd(f, (*s)[n+1])
fmt.Printf("%d,%d: gcd(%d, %d) = %d\n", n+1, n+2, f, (*s)[n+1], g)
if g != 1 {
panic("oh no!")
return
}
}
}

// gcd copied from greatest common divisor task
func gcd(x, y int) int {
for y != 0 {
x, y = y, x%y
}
return x
}
```
```// SB implements the Stern-Brocot sequence.
//
// Generator() satisfies RC Task 1.  For remaining tasks, Generator could be
// used but FirstN(), and Find() are simpler methods for specific stopping
// criteria.  FirstN and Find might also be considered to satisfy Task 1,
// in which case Generator would not really be needed.  Anyway, there it is.
package sb

// Seq represents an even number of terms of a Stern-Brocot sequence.
//
// (Specifically, the zeroth term, 0, given in OEIS A002487 is not represented.)
// Term 1 (== 1) is stored at slice index 0.
//
// Methods on Seq rely on Seq always containing an even number of terms.
type Seq []int

// New returns a Seq with the two base terms.
func New() *Seq {
return &Seq{1, 1} // Step 1 of the RC task.
}

// TwoMore appends two more terms to p.
// It's the body of the loop in the RC algorithm.
// Generate(), FirstN(), and Find() wrap this body in different ways.
func (p *Seq) TwoMore() {
s := *p
n := len(s) / 2 // Steps 2 and 5 of the RC task.
c := s[n]
*p = append(s, c+s[n-1], c) // Steps 3 and 4 of the RC task.
}

// Generator returns a generator function that returns successive terms
// (until overflow.)
func Generator() func() int {
n := 0
p := New()
return func() int {
if len(*p) == n {
p.TwoMore()
}
t := (*p)[n]
n++
return t
}
}

// FirstN lazily extends p as needed so that it has at least n terms.
// FirstN then returns a list of the first n terms.
func (p *Seq) FirstN(n int) []int {
for len(*p) < n {
p.TwoMore()
}
return []int((*p)[:n])
}

// Find lazily extends p as needed until it contains the value x
// Find then returns the slice index of x in p.
func (p *Seq) Find(x int) int {
for n, f := range *p {
if f == x {
return n
}
}
for {
p.TwoMore()
switch x {
case (*p)[len(*p)-2]:
return len(*p) - 2
case (*p)[len(*p)-1]:
return len(*p) - 1
}
}
}
```
Output:
```First 15:
1:  1
2:  1
3:  2
4:  1
5:  3
6:  2
7:  3
8:  1
9:  4
10:  3
11:  5
12:  2
13:  5
14:  3
15:  4
First 15: [1 1 2 1 3 2 3 1 4 3 5 2 5 3 4]
1 at 1-based index 1
2 at 1-based index 3
3 at 1-based index 5
4 at 1-based index 9
5 at 1-based index 11
6 at 1-based index 33
7 at 1-based index 19
8 at 1-based index 21
9 at 1-based index 35
10 at 1-based index 39
100 at 1-based index 1179
1-based indexes: gcd
1,2: gcd(1, 1) = 1
2,3: gcd(1, 2) = 1
3,4: gcd(2, 1) = 1
4,5: gcd(1, 3) = 1
...
998,999: gcd(27, 38) = 1
999,1000: gcd(38, 11) = 1
```

```import Data.List (elemIndex)

sb :: [Int]
sb = 1 : 1 : f (tail sb) sb
where
f (a : aa) (b : bb) = a + b : a : f aa bb

main :: IO ()
main = do
print \$ take 15 sb
print
[ (i, 1 + (\(Just i) -> i) (elemIndex i sb))
| i <- [1 .. 10] <> [100]
]
print \$
all (\(a, b) -> 1 == gcd a b) \$
take 1000 \$ zip sb (tail sb)
```
Output:
```[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```

Or, expressed in terms of iterate:

```import Data.Function (on)
import Data.List (nubBy, sortOn)
import Data.Ord (comparing)

------------------ STERN-BROCOT SEQUENCE -----------------

sternBrocot :: [Int]
sternBrocot = head <\$> iterate go [1, 1]
where
go (a : b : xs) = (b : xs) <> [a + b, b]

--------------------------- TEST -------------------------
main :: IO ()
main = do
print \$ take 15 sternBrocot
print \$
take 10 \$
nubBy (on (==) fst) \$
sortOn fst \$
takeWhile ((110 >=) . fst) \$
zip sternBrocot [1 ..]
print \$
take 1 \$
dropWhile ((100 /=) . fst) \$
zip sternBrocot [1 ..]
print \$
(all ((1 ==) . uncurry gcd) . (zip <*> tail)) \$
take 1000 sternBrocot
```
Output:
```[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```

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:

```sternbrocot=:1 :0
ind=. 0
seq=. 1 1
while. -. u seq do.
ind=. ind+1
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: `u sternbrocot`. 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.)

First fifteen members of the sequence:

```   15{.(15<:#) sternbrocot
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+(10 e. ]) sternbrocot i.1+i.10
1 3 5 9 11 33 19 21 35 39
```

One based index of where the number 100 first appears:

```   1+(100 e. ]) sternbrocot i. 100
1179
```

List of distinct greatest common divisors of adjacent number pairs from a sternbrocot sequence which includes the first 1000 elements:

```   ~.2 +./\ (1000<:#) sternbrocot
1
```

Java

Works with: Java version 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 `gcd` method from `BigInteger` rather than using its own.

```import java.math.BigInteger;

public class SternBrocot {
}};

private static void genSeq(int n){
for(int conIdx = 1; sequence.size() < n; conIdx++){
int consider = sequence.get(conIdx);
int pre = sequence.get(conIdx - 1);
}

}

public static void main(String[] args){
genSeq(1200);
System.out.println("The first 15 elements are: " + sequence.subList(0, 15));
for(int i = 1; i <= 10; i++){
System.out.println("First occurrence of " + i + " is at " + (sequence.indexOf(i) + 1));
}

System.out.println("First occurrence of 100 is at " + (sequence.indexOf(100) + 1));

boolean failure = false;
for(int i = 0; i < 999; i++){
failure |= !BigInteger.valueOf(sequence.get(i)).gcd(BigInteger.valueOf(sequence.get(i + 1))).equals(BigInteger.ONE);
}
System.out.println("All GCDs are" + (failure ? " not" : "") + " 1");
}
}
```
Output:
```The first 15 elements are: [1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]
First occurrence of 1 is at 1
First occurrence of 2 is at 3
First occurrence of 3 is at 5
First occurrence of 4 is at 9
First occurrence of 5 is at 11
First occurrence of 6 is at 33
First occurrence of 7 is at 19
First occurrence of 8 is at 21
First occurrence of 9 is at 35
First occurrence of 10 is at 39
First occurrence of 100 is at 1179
All GCDs are 1```

Stern-Brocot Tree

Works with: Java version 8
```import java.awt.*;
import javax.swing.*;

public class SternBrocot extends JPanel {

public SternBrocot() {
setPreferredSize(new Dimension(800, 500));
setFont(new Font("Arial", Font.PLAIN, 18));
setBackground(Color.white);
}

private void drawTree(int n1, int d1, int n2, int d2,
int x, int y, int gap, int lvl, Graphics2D g) {

if (lvl == 0)
return;

// mediant
int numer = n1 + n2;
int denom = d1 + d2;

if (lvl > 1) {
g.drawLine(x + 5, y + 4, x - gap + 5, y + 124);
g.drawLine(x + 5, y + 4, x + gap + 5, y + 124);
}

g.setColor(getBackground());
g.fillRect(x - 10, y - 15, 35, 40);

g.setColor(getForeground());
g.drawString(String.valueOf(numer), x, y);
g.drawString("_", x, y + 2);
g.drawString(String.valueOf(denom), x, y + 22);

drawTree(n1, d1, numer, denom, x - gap, y + 120, gap / 2, lvl - 1, g);
drawTree(numer, denom, n2, d2, x + gap, y + 120, gap / 2, lvl - 1, g);
}

@Override
public void paintComponent(Graphics gg) {
super.paintComponent(gg);
Graphics2D g = (Graphics2D) gg;
g.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
RenderingHints.VALUE_ANTIALIAS_ON);

int w = getWidth();

drawTree(0, 1, 1, 0, w / 2, 50, w / 4, 4, g);
}

public static void main(String[] args) {
SwingUtilities.invokeLater(() -> {
JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.setTitle("Stern-Brocot Tree");
f.setResizable(false);
f.pack();
f.setLocationRelativeTo(null);
f.setVisible(true);
});
}
}
```

JavaScript

```(() => {
'use strict';

const main = () => {

// sternBrocot :: Generator [Int]
const sternBrocot = () => {
const go = xs => {
const x = snd(xs);
return tail(append(xs, [fst(xs) + x, x]));
};
};

// TESTS ------------------------------------------
const
sbs = take(1200, sternBrocot()),
ixSB = zip(sbs, enumFrom(1));

return unlines(map(
JSON.stringify,
[
take(15, sbs),
take(10,
map(listFromTuple,
nubBy(
on(eq, fst),
sortBy(
comparing(fst),
takeWhile(x => 12 !== fst(x), ixSB)
)
)
)
),
listFromTuple(
take(1, dropWhile(x => 100 !== fst(x), ixSB))[0]
),
all(tpl => 1 === gcd(fst(tpl), snd(tpl)),
take(1000, zip(sbs, tail(sbs)))
)
]
));
};

// GENERIC ABSTRACTIONS -------------------------------

// Just :: a -> Maybe a
const Just = x => ({
type: 'Maybe',
Nothing: false,
Just: x
});

// Nothing :: Maybe a
const Nothing = () => ({
type: 'Maybe',
Nothing: true,
});

// Tuple (,) :: a -> b -> (a, b)
const Tuple = (a, b) => ({
type: 'Tuple',
'0': a,
'1': b,
length: 2
});

// | Absolute value.

// abs :: Num -> Num
const abs = Math.abs;

// Determines whether all elements of the structure
// satisfy the predicate.

// all :: (a -> Bool) -> [a] -> Bool
const all = (p, xs) => xs.every(p);

// append (++) :: [a] -> [a] -> [a]
// append (++) :: String -> String -> String
const append = (xs, ys) => xs.concat(ys);

// chr :: Int -> Char
const chr = String.fromCodePoint;

// comparing :: (a -> b) -> (a -> a -> Ordering)
const comparing = f =>
(x, y) => {
const
a = f(x),
b = f(y);
return a < b ? -1 : (a > b ? 1 : 0);
};

// dropWhile :: (a -> Bool) -> [a] -> [a]
// dropWhile :: (Char -> Bool) -> String -> String
const dropWhile = (p, xs) => {
const lng = xs.length;
return 0 < lng ? xs.slice(
until(
i => i === lng || !p(xs[i]),
i => 1 + i,
0
)
) : [];
};

// enumFrom :: a -> [a]
function* enumFrom(x) {
let v = x;
while (true) {
yield v;
v = succ(v);
}
}

// eq (==) :: Eq a => a -> a -> Bool
const eq = (a, b) => {
const t = typeof a;
return t !== typeof b ? (
false
) : 'object' !== t ? (
'function' !== t ? (
a === b
) : a.toString() === b.toString()
) : (() => {
const aks = Object.keys(a);
return aks.length !== Object.keys(b).length ? (
false
) : aks.every(k => eq(a[k], b[k]));
})();
};

// fmapGen <\$> :: (a -> b) -> Gen [a] -> Gen [b]
function* fmapGen(f, gen) {
const g = gen;
let v = take(1, g)[0];
while (0 < v.length) {
yield(f(v))
v = take(1, g)[0]
}
}

// fst :: (a, b) -> a
const fst = tpl => tpl[0];

// gcd :: Int -> Int -> Int
const gcd = (x, y) => {
const
_gcd = (a, b) => (0 === b ? a : _gcd(b, a % b)),
abs = Math.abs;
return _gcd(abs(x), abs(y));
};

// head :: [a] -> a
const head = xs => xs.length ? xs[0] : undefined;

// isChar :: a -> Bool
const isChar = x =>
('string' === typeof x) && (1 === x.length);

// iterate :: (a -> a) -> a -> Gen [a]
function* iterate(f, x) {
let v = x;
while (true) {
yield(v);
v = f(v);
}
}

// Returns Infinity over objects without finite length
// this enables zip and zipWith to choose the shorter
// argument when one is non-finite, like cycle, repeat etc

// length :: [a] -> Int
const length = xs => xs.length || Infinity;

// listFromTuple :: (a, a ...) -> [a]
const listFromTuple = tpl =>
Array.from(tpl);

// map :: (a -> b) -> [a] -> [b]
const map = (f, xs) => xs.map(f);

// nubBy :: (a -> a -> Bool) -> [a] -> [a]
const nubBy = (p, xs) => {
const go = xs => 0 < xs.length ? (() => {
const x = xs[0];
return [x].concat(
go(xs.slice(1)
.filter(y => !p(x, y))
)
)
})() : [];
return go(xs);
};

// e.g. sortBy(on(compare,length), xs)

// on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
const on = (f, g) => (a, b) => f(g(a), g(b));

// ord :: Char -> Int
const ord = c => c.codePointAt(0);

// snd :: (a, b) -> b
const snd = tpl => tpl[1];

// sortBy :: (a -> a -> Ordering) -> [a] -> [a]
const sortBy = (f, xs) =>
xs.slice()
.sort(f);

// succ :: Enum a => a -> a
const succ = x =>
isChar(x) ? (
chr(1 + ord(x))
) : isNaN(x) ? (
undefined
) : 1 + x;

// tail :: [a] -> [a]
const tail = xs => 0 < xs.length ? xs.slice(1) : [];

// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = (n, xs) =>
xs.constructor.constructor.name !== 'GeneratorFunction' ? (
xs.slice(0, n)
) : [].concat.apply([], Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}));

// takeWhile :: (a -> Bool) -> [a] -> [a]
// takeWhile :: (Char -> Bool) -> String -> String
const takeWhile = (p, xs) =>
xs.constructor.constructor.name !==
'GeneratorFunction' ? (() => {
const lng = xs.length;
return 0 < lng ? xs.slice(
0,
until(
i => lng === i || !p(xs[i]),
i => 1 + i,
0
)
) : [];
})() : takeWhileGen(p, xs);

// takeWhileGen :: (a -> Bool) -> Gen [a] -> [a]
const takeWhileGen = (p, xs) => {
const ys = [];
let
nxt = xs.next(),
v = nxt.value;
while (!nxt.done && p(v)) {
ys.push(v);
nxt = xs.next();
v = nxt.value
}
return ys;
};

// uncons :: [a] -> Maybe (a, [a])
const uncons = xs => {
const lng = length(xs);
return (0 < lng) ? (
lng < Infinity ? (
Just(Tuple(xs[0], xs.slice(1))) // Finite list
) : (() => {
const nxt = take(1, xs);
return 0 < nxt.length ? (
Just(Tuple(nxt[0], xs))
) : Nothing();
})() // Lazy generator
) : Nothing();
};

// unlines :: [String] -> String
const unlines = xs => xs.join('\n');

// until :: (a -> Bool) -> (a -> a) -> a -> a
const until = (p, f, x) => {
let v = x;
while (!p(v)) v = f(v);
return v;
};

// Use of `take` and `length` here allows for zipping with non-finite
// lists - i.e. generators like cycle, repeat, iterate.

// zip :: [a] -> [b] -> [(a, b)]
const zip = (xs, ys) => {
const lng = Math.min(length(xs), length(ys));
return Infinity !== lng ? (() => {
const bs = take(lng, ys);
return take(lng, xs).map((x, i) => Tuple(x, bs[i]));
})() : zipGen(xs, ys);
};

// zipGen :: Gen [a] -> Gen [b] -> Gen [(a, b)]
const zipGen = (ga, gb) => {
function* go(ma, mb) {
let
a = ma,
b = mb;
while (!a.Nothing && !b.Nothing) {
let
ta = a.Just,
tb = b.Just
yield(Tuple(fst(ta), fst(tb)));
a = uncons(snd(ta));
b = uncons(snd(tb));
}
}
return go(uncons(ga), uncons(gb));
};

// MAIN ---
return main();
})();
```
Output:
```[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```

jq

Works with: jq version 1.4

In jq 1.4, there is no equivalent of "yield" for unbounded streams, and so the following uses "until".

Foundations:

```def until(cond; update):
def _until:
if cond then . else (update | _until) end;
try _until catch if .== "break" then empty else . end ;

def gcd(a; b):
# subfunction expects [a,b] as input
# i.e. a ~ .[0] and b ~ .[1]
def rgcd: if .[1] == 0 then .[0]
else [.[1], .[0] % .[1]] | rgcd
end;
[a,b] | rgcd ;```

The A002487 integer sequence:

The following definition is in strict accordance with https://oeis.org/A002487: i.e. a(0) = 0, a(1) = 1; for n > 0: a(2*n) = a(n), a(2*n+1) = a(n) + a(n+1). 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.

```# If n is non-negative, then A002487(n)
# generates an array with at least n elements of
# the A002487 sequence;
# if n is negative, elements are added until (-n)
# is found.
def A002487(n):
[0,1]
| until(
length as \$l
| if n >= 0 then \$l >= n
else      .[\$l-1] == -n
end;
length as \$l
| (\$l / 2) as \$n
| .[\$l] = .[\$n]
| if (.[\$l-2] == -n) then .
else .[\$l + 1] = .[\$n] + .[\$n+1]
end ) ;```

```# Generate a stream of n integers beginning with 1,1...
def stern_brocot(n): A002487(n+1) | .[1:n+1][];

# Return the index (counting from 1) of n in the
# sequence starting with 1,1,...
def stern_brocot_index(n):
A002487(-n) | length -1 ;

(range(1;11), 100) as \$i
| "index of \(\$i) is \(stern_brocot_index(\$i))" ;

A002487(1000)
| . as \$A
| reduce range(0; length-1) as \$i
( [];
gcd( \$A[\$i]; \$A[\$i+1] ) as \$gcd
| if \$gcd == 1 then . else . +  [\$gcd] end)
| if length == 0 then "GCDs are all 1"
else "GCDs include \(.)" end ;

"First 15 integers of the Stern-Brocot sequence",
"as defined in the task description are:",
stern_brocot(15),
"",
"Using an index origin of 1:",
"",
Output:
```\$ jq -r -n -f stern_brocot.jq
First 15 integers of the Stern-Brocot sequence
as defined in the task description are:
1
1
2
1
3
2
3
1
4
3
5
2
5
3
4

Using an index origin of 1:
index of 1 is 1
index of 2 is 3
index of 3 is 5
index of 4 is 9
index of 5 is 11
index of 6 is 33
index of 7 is 19
index of 8 is 21
index of 9 is 35
index of 10 is 39
index of 100 is 1179

GCDs are all 1
```

Julia

Translation of: Python
```using Printf

function sternbrocot(f::Function=(x) -> length(x) ≥ 20)::Vector{Int}
rst = Int[1, 1]
i = 2
while !f(rst)
append!(rst, Int[rst[i] + rst[i-1], rst[i]])
i += 1
end
return rst
end

println("First 15 elements of Stern-Brocot series:\n", sternbrocot(x -> length(x) ≥ 15)[1:15], "\n")

for i in (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100)
occurr = findfirst(x -> x == i, sternbrocot(x -> i ∈ x))
@printf("Index of first occurrence of %3i in the series: %4i\n", i, occurr)
end

print("\nAssertion: the greatest common divisor of all the two\nconsecutive members of the series up to the 1000th member, is always one: ")
sb = sternbrocot(x -> length(x) > 1000)
if all(gcd(prev, this) == 1 for (prev, this) in zip(sb[1:1000], sb[2:1000]))
println("Confirmed.")
else
println("Rejected.")
end
```
Output:
```First 15 elements of Stern-Brocot series:
[1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]

Index of first occurrence of   1 in the series:    1
Index of first occurrence of   2 in the series:    3
Index of first occurrence of   3 in the series:    5
Index of first occurrence of   4 in the series:    9
Index of first occurrence of   5 in the series:   11
Index of first occurrence of   6 in the series:   33
Index of first occurrence of   7 in the series:   19
Index of first occurrence of   8 in the series:   21
Index of first occurrence of   9 in the series:   35
Index of first occurrence of  10 in the series:   39
Index of first occurrence of 100 in the series: 1179

Assertion: the greatest common divisor of all the two
consecutive members of the series up to the 1000th member, is always one: Confirmed.```

Kotlin

```// version 1.1.0

val sbs = mutableListOf(1, 1)

fun sternBrocot(n: Int, fromStart: Boolean = true) {
if (n < 4 || (n % 2 != 0)) throw IllegalArgumentException("n must be >= 4 and even")
var consider = if (fromStart) 1 else n / 2 - 1
while (true) {
val sum = sbs[consider] + sbs[consider - 1]
if (sbs.size == n) break
consider++
}
}

fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)

fun main(args: Array<String>) {
var n = 16  // needs to be even to ensure 'considered' number is added
println("First 15 members of the Stern-Brocot sequence")
sternBrocot(n)
println(sbs.take(15))

val firstFind = IntArray(11)  // all zero by default
firstFind[0] = -1 // needs to be non-zero for subsequent test
for ((i, v) in sbs.withIndex())
if (v <= 10 && firstFind[v] == 0) firstFind[v] = i + 1
loop@ while (true) {
n += 2
sternBrocot(n, false)
val vv = sbs.takeLast(2)
var m = n - 1
for (v in vv) {
if (v <= 10 && firstFind[v] == 0) firstFind[v] = m
if (firstFind.all { it != 0 }) break@loop
m++
}
}
println("\nThe numbers 1 to 10 first appear at the following indices:")
for (i in 1..10) println("\${"%2d".format(i)} -> \${firstFind[i]}")

print("\n100 first appears at index ")
while (true) {
n += 2
sternBrocot(n, false)
val vv = sbs.takeLast(2)
if (vv[0] == 100) {
println(n - 1); break
}
if (vv[1] == 100) {
println(n); break
}
}

print("\nThe GCDs of each pair of the series up to the 1000th member are ")
for (p in 0..998 step 2) {
if (gcd(sbs[p], sbs[p + 1]) != 1) {
println("not all one")
return
}
}
println("all one")
}
```
Output:
```First 15 members of the Stern-Brocot sequence
[1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]

The numbers 1 to 10 first appear at the following indices:
1 -> 1
2 -> 3
3 -> 5
4 -> 9
5 -> 11
6 -> 33
7 -> 19
8 -> 21
9 -> 35
10 -> 39

100 first appears at index 1179

The GCDs of each pair of the series up to the 1000th member are all one
```

Lua

```-- Task 1
function sternBrocot (n)
local sbList, pos, c = {1, 1}, 2
repeat
c = sbList[pos]
table.insert(sbList, c + sbList[pos - 1])
table.insert(sbList, c)
pos = pos + 1
until #sbList >= n
return sbList
end

-- Return index in table 't' of first value matching 'v'
function findFirst (t, v)
for key, value in pairs(t) do
if v then
if value == v then return key end
else
if value ~= 0 then return key end
end
end
return nil
end

-- Return greatest common divisor of 'x' and 'y'
function gcd (x, y)
if y == 0 then
return math.abs(x)
else
return gcd(y, x % y)
end
end

-- Check GCD of adjacent values in 't' up to 1000 is always 1
for pos = 1, 1000 do
if gcd(t[pos], t[pos + 1]) ~= 1 then return "FAIL" end
end
return "PASS"
end

-- Main procedure
local sb = sternBrocot(10000)
for n = 1, 15 do io.write(sb[n] .. " ") end
for i = 1, 10 do print("\t" .. i, findFirst(sb, i)) end
print("\nTask 4: " .. findFirst(sb, 100))
```
Output:
```Task 2: 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

MACRO-11

```        .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
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\$
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```
Output:
```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.```

```            NORMAL MODE IS INTEGER
VECTOR VALUES FRST15 = \$20HFIRST 15 NUMBERS ARE*\$
VECTOR VALUES FRSTAT = \$6HFIRST ,I3,S1,11HAPPEARS AT ,I4*\$
VECTOR VALUES NUMBER = \$I4*\$

DIMENSION STERN(1200)
STERN(1) = 1
STERN(2) = 1

R GENERATE FIRST 1200 MEMBERS OF THE STERN-BROCOT SEQUENCE
THROUGH GENSEQ, FOR I = 1, 1, I .GE. 600
STERN(I*2-1) = STERN(I) + STERN(I-1)
GENSEQ      STERN(I*2) = STERN(I)

R PRINT FIRST 15 VALUES OF STERN-BROCOT SEQUENCE
PRINT FORMAT FRST15
THROUGH P15, FOR I = 1, 1, I .G. 15
P15         PRINT ON LINE FORMAT NUMBER, STERN(I)

R PRINT FIRST OCCURRENCE OF 1..10
THROUGH FRST10, FOR I = 1, 1, I .G. 10
FRST10      PRINT FORMAT FRSTAT, I, FIRST.(I)
PRINT FORMAT FRSTAT, 100, FIRST.(100)

R SEARCH FOR FIRST OCCURRENCE OF N IN SEQUENCE
INTERNAL FUNCTION(N)
ENTRY TO FIRST.
THROUGH SCAN, FOR K = 1, 1, I .G. 1200
SCAN        WHENEVER N .E. STERN(K), FUNCTION RETURN K
END OF FUNCTION
END OF PROGRAM```
Output:
```FIRST 15 NUMBERS ARE
1
1
2
1
3
2
3
1
4
3
5
2
5
3
4
FIRST   1 APPEARS AT    1
FIRST   2 APPEARS AT    3
FIRST   3 APPEARS AT    5
FIRST   4 APPEARS AT    9
FIRST   5 APPEARS AT   11
FIRST   6 APPEARS AT   33
FIRST   7 APPEARS AT   19
FIRST   8 APPEARS AT   21
FIRST   9 APPEARS AT   35
FIRST  10 APPEARS AT   39
FIRST 100 APPEARS AT 1179```

Mathematica / Wolfram Language

```sb = {1, 1};
Do[
sb = sb~Join~{Total@sb[[i - 1 ;; i]], sb[[i]]}
,
{i, 2, 1000}
]
Take[sb, 15]
Flatten[FirstPosition[sb, #] & /@ Range[10]]
First@FirstPosition[sb, 100]
AllTrue[Partition[Take[sb, 1000], 2, 1], Apply[GCD] /* EqualTo[1]]
```
Output:
```{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
True```

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```
Output:
```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```

Modula-2

```MODULE SternBrocot;
FROM InOut IMPORT WriteString, WriteCard, WriteLn;

CONST Amount = 1200;

VAR stern: ARRAY [1..Amount] OF CARDINAL;
i: CARDINAL;

PROCEDURE GCD(a,b: CARDINAL): CARDINAL;
VAR c: CARDINAL;
BEGIN
WHILE b # 0 DO
c := a MOD b;
a := b;
b := c;
END;
RETURN a;
END GCD;

PROCEDURE Generate;
VAR i: CARDINAL;
BEGIN
stern[1] := 1;
stern[2] := 1;
FOR i := 2 TO Amount DIV 2 DO
stern[i*2 - 1] := stern[i] + stern[i-1];
stern[i*2] := stern[i];
END;
END Generate;

PROCEDURE FindFirst(n: CARDINAL): CARDINAL;
VAR i: CARDINAL;
BEGIN
FOR i := 1 TO Amount DO
IF stern[i] = n THEN
RETURN i;
END;
END;
END FindFirst;

PROCEDURE ShowFirst(n: CARDINAL);
BEGIN
WriteString("First");
WriteCard(n,4);
WriteString(" at ");
WriteCard(FindFirst(n), 4);
WriteLn;
END ShowFirst;

BEGIN
Generate;

WriteString("First 15 numbers:");
FOR i := 1 TO 15 DO
WriteCard(stern[i], 2);
END;
WriteLn;

FOR i := 1 TO 10 DO
ShowFirst(i);
END;
ShowFirst(100);
WriteLn;

FOR i := 2 TO Amount DO
IF GCD(stern[i-1], stern[i]) # 1 THEN
WriteString("GCD of adjacent elements not 1 at: ");
WriteCard(i-1, 4);
WriteLn;
HALT;
END;
END;
WriteString("The GCD of every pair of adjacent elements is 1.");
WriteLn;
END SternBrocot.
```
Output:
```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.```

Nim

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.

```import math, strformat, strutils

iterator sternBrocot(): (int, int) =
## Yield index and value of the terms of the sequence.
var sequence: seq[int]
var index = 1
yield (1, 1)
yield (2, 1)
while true:
sequence.add sequence[index] + sequence[index - 1]
yield (sequence.len, sequence[^1])
yield (sequence.len, sequence[^1])
inc index

# Fiind first 15 terms.
var res: seq[int]
for i, n in sternBrocot():
if i == 15: break
echo "First 15 terms: ", res.join(" ")
echo()

# Find indexes for 1..10.
var indexes: array[1..10, int]
var toFind = 10
for i, n in sternBrocot():
if n in 1..10 and indexes[n] == 0:
indexes[n] = i
dec toFind
if toFind == 0: break
for n in 1..10:
echo &"Index of first occurrence of number {n:3}: {indexes[n]:4}"

# Find index for 100.
var index: int
for i, n in sternBrocot():
if n == 100:
index = i
break
echo &"Index of first occurrence of number 100: {index:4}"
echo()

# Check GCD.
var prev = 1
index = 1
for i, n in sternBrocot():
if gcd(prev, n) != 1: break
prev = n
inc index
if index > 1000: break
if index <= 1000:
echo "Found two successive terms at index: ", index
else:
echo "All consecutive terms up to the 1000th member have a GCD equal to one."
```
Output:
```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.```

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
```
Tests:
```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"
```
Output:
``` 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
```

Oforth

```: stern(n)
| l i |
n 1- 2 / loop: i [ l at(i) l at(i 1+) tuck + l add l add ]
n 2 mod ifFalse: [ dup removeLast drop ] dup freeze ;

stern(10000) Constant new: Sterns```
Output:
```>Sterns left(15) .
[1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4] ok

>10 seq apply(#[ dup . Sterns indexOf . printcr ])
1 1
2 3
3 5
4 9
5 11
6 33
7 19
8 21
9 35
10 39
ok

>Sterns indexOf(100) .
1179 ok

>999 seq map(#[ dup Sterns at swap 1 + Sterns at gcd ]) conform(#[ 1 == ]) .
1 ok
>
```

PARI/GP

Works with: PARI/GP version 2.7.4 and above
```\\ Stern-Brocot sequence
\\ 5/27/16 aev
SternBrocot(n)={
my(L=List([1,1]),k=2); if(n<3,return(L));
for(i=2,n, listput(L,L[i]+L[i-1]); if(k++>=n, break); listput(L,L[i]);if(k++>=n, break));
return(Vec(L));
}
\\ Find the first item in any list starting with sind index (return 0 or index).
\\ 9/11/2015 aev
findinlist(list, item, sind=1)={
my(idx=0, ln=#list); if(ln==0 || sind<1 || sind>ln, return(0));
for(i=sind, ln, if(list[i]==item, idx=i; break;)); return(idx);
}
{
\\ Required tests:
my(v,j);
v=SternBrocot(15);
print1("The first 15: "); print(v);
v=SternBrocot(1200);
print1("The first i@n: "); \\print(v);
for(i=1,10, if(j=findinlist(v,i), print1(i,"@",j,", ")));
if(j=findinlist(v,100), print(100,"@",j));
v=SternBrocot(10000);
print1("All GCDs=1?: ");
j=1; for(i=2,10000, j*=gcd(v[i-1],v[i]));
if(j==1, print("Yes"), print("No"));
}```
Output:
```The first 15: [1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]
The first i@n: 1@1, 2@3, 3@5, 4@9, 5@11, 6@33, 7@19, 8@21, 9@35, 10@39, 100@1179
All GCDs=1?: Yes
```

Pascal

Works with: Free Pascal
```program StrnBrCt;
{\$IFDEF FPC}
{\$MODE DELPHI}
{\$ENDIF}
const
MaxCnt = 10835282;{ seq[i] < 65536 = high(Word) }
//MaxCnt = 500*1000*1000;{ 2Gbyte -> real 0.85 s user 0.31 }
type
tSeqdata =  word;//cardinal LongWord
pSeqdata = pWord;//pcardinal pLongWord
tseq = array of tSeqdata;

function SternBrocotCreate(size:NativeInt):tseq;
var
pSeq,pIns : pSeqdata;
PosIns : NativeInt;
sum : tSeqdata;
Begin
setlength(result,Size+1);
dec(Size); //== High(result)
pIns := @result[size];// set at end
PosIns := -size+2;    // negative index campare to 0
pSeq := @result[0];

sum := 1;
pSeq[0]:= sum;pSeq[1]:= sum;
repeat
pIns[PosIns+1] := sum;//append copy of considered
inc(sum,pSeq[0]);
pIns[PosIns  ] := sum;
inc(pSeq);
inc(PosIns,2);sum := pSeq[1];//aka considered
until PosIns>= 0;
setlength(result,length(result)-1);
end;

function FindIndex(const s:tSeq;value:tSeqdata):NativeInt;
Begin
result := 0;
while result <= High(s) do
Begin
if s[result] = value then
EXIT(result+1);
inc(result);
end;
end;

function gcd_iterative(u, v: NativeInt): NativeInt;
//http://rosettacode.org/wiki/Greatest_common_divisor#Pascal_.2F_Delphi_.2F_Free_Pascal
var
t: NativeInt;
begin
while v <> 0 do begin
t := u;u := v;v := t mod v;
end;
gcd_iterative := abs(u);
end;

var
seq : tSeq;
i : nativeInt;
Begin
seq:= SternBrocotCreate(MaxCnt);
// Show the first fifteen members of the sequence.
For i := 0 to 13 do write(seq[i],',');writeln(seq[14]);
//Show the (1-based) index of where the numbers 1-to-10 first appears in the
For i := 1 to 10 do
write(i,' @ ',FindIndex(seq,i),',');
writeln(#8#32);
//Show the (1-based) index of where the number 100 first appears in the sequence.
writeln(100,' @ ',FindIndex(seq,100));
//Check that the greatest common divisor of all the two consecutive members of the series up to the 1000th member, is always one.
i := 999;
if i > High(seq) then
i := High(seq);
Repeat
IF gcd_iterative(seq[i],seq[i+1]) <>1 then
Begin
writeln(' failure at  ',i+1,'  ',seq[i],'  ',seq[i+1]);
BREAK;
end;
dec(i);
until i <0;
IF i< 0 then
writeln('GCD-test is O.K.');
setlength(seq,0);
end.
```
Output:
```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 @ 38,8 @ 42,9 @ 47,10 @ 57
100 @ 1179

GCD-test is O.K.```

Perl

```use strict;
use warnings;

sub stern_brocot {
my @list = (1, 1);
sub {
push @list, \$list[0] + \$list[1], \$list[1];
shift @list;
}
}

{
my \$generator = stern_brocot;
print join ' ', map &\$generator, 1 .. 15;
print "\n";
}

for (1 .. 10, 100) {
my \$index = 1;
my \$generator = stern_brocot;
\$index++ until \$generator->() == \$_;
print "first occurrence of \$_ is at index \$index\n";
}

{
sub gcd {
my (\$u, \$v) = @_;
\$v ? gcd(\$v, \$u % \$v) : abs(\$u);
}
my \$generator = stern_brocot;
my (\$a, \$b) = (\$generator->(), \$generator->());
for (1 .. 1000) {
die "unexpected GCD for \$a and \$b" unless gcd(\$a, \$b) == 1;
(\$a, \$b) = (\$b, \$generator->());
}
}
```
Output:
```1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
first occurrence of 1 is at index 1
first occurrence of 2 is at index 3
first occurrence of 3 is at index 5
first occurrence of 4 is at index 9
first occurrence of 5 is at index 11
first occurrence of 6 is at index 33
first occurrence of 7 is at index 19
first occurrence of 8 is at index 21
first occurrence of 9 is at index 35
first occurrence of 10 is at index 39
first occurrence of 100 is at index 1179```

A slightly different method:

Library: ntheory
```use ntheory qw/gcd vecsum vecfirst/;

sub stern_diatomic {
my (\$p,\$q,\$i) = (0,1,shift);
while (\$i) {
if (\$i & 1) { \$p += \$q; } else { \$q += \$p; }
\$i >>= 1;
}
\$p;
}

my @s = map { stern_diatomic(\$_) } 1..15;
print "First fifteen: [@s]\n";
@s = map { my \$n=\$_; vecfirst { stern_diatomic(\$_) == \$n } 1..10000 } 1..10;
print "Index of 1-10 first occurrence: [@s]\n";
print "Index of 100 first occurrence: ", (vecfirst { stern_diatomic(\$_) == 100 } 1..10000), "\n";
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";
```
Output:
```First fifteen: [1 1 2 1 3 2 3 1 4 3 5 2 5 3 4]
Index of 1-10 first occurrence: [1 3 5 9 11 33 19 21 35 39]
Index of 100 first occurrence: 1179
The first 999 consecutive pairs are all coprime.```

Phix

```sequence sb = {1,1}
integer c = 2

function stern_brocot(integer n)
while length(sb)<n do
sb &= sb[c]+sb[c-1] & sb[c]
c += 1
end while
return sb[1..n]
end function

sequence s = stern_brocot(15)
puts(1,"first 15:")
?s
integer n = 16, k
sequence idx = tagset(10)
for i=1 to length(idx) do
while 1 do
k = find(idx[i],s)
if k!=0 then exit end if
n *= 2
s = stern_brocot(n)
end while
idx[i] = k
end for
puts(1,"indexes of 1..10:")
?idx
puts(1,"index of 100:")
while 1 do
k = find(100,s)
if k!=0 then exit end if
n *= 2
s = stern_brocot(n)
end while
?k
s = stern_brocot(1000)
integer maxgcd = 1
for i=1 to 999 do
maxgcd = max(gcd(s[i],s[i+1]),maxgcd)
end for
printf(1,"max gcd:%d\n",{maxgcd})
```
Output:
```first 15:{1,1,2,1,3,2,3,1,4,3,5,2,5,3,4}
indexes of 1..10:{1,3,5,9,11,33,19,21,35,39}
index of 100:1179
max gcd:1
```

PicoLisp

Translation of: C

Using the gcd function defined at Greatest_common_divisor#PicoLisp:

```(de nmbr (N)
(let (A 1  B 0)
(while (gt0 N)
(if (bit? 1 N)
(inc 'B A)
(inc 'A B) )
(setq N (>> 1 N)) )
B ) )

(let Lst (mapcar nmbr (range 1 2000))
(for N 10
(println 'First N 'found 'at: (index N Lst)) )
(println 'First 100 'found 'at: (index 100 Lst))
(for (L Lst (cdr L) (cddr L))
(test 1 (gcd (car L) (cadr L))) )
(prinl "All consecutive pairs are relative prime!") )```
Output:
```First-15: (1 1 2 1 3 2 3 1 4 3 5 2 5 3 4)
First 1 found at: 1
First 2 found at: 3
First 3 found at: 5
First 4 found at: 9
First 5 found at: 11
First 6 found at: 33
First 7 found at: 19
First 8 found at: 21
First 9 found at: 35
First 10 found at: 39
First 100 found at: 1179
All consecutive pairs are relative prime!
```

PL/I

```sternBrocot: procedure options(main);
%replace MAX by 1200;
declare S(1:MAX) fixed;

/* find the first occurrence of N in S */
findFirst: procedure(n) returns(fixed);
declare (n, i) fixed;
do i=1 to MAX;
if S(i)=n then return(i);
end;
end findFirst;

/* find the greatest common divisor of A and B */
gcd: procedure(a, b) returns(fixed) recursive;
declare (a, b) fixed;
if b = 0 then return(a);
return(gcd(b, mod(a, b)));
end gcd;

/* calculate S(i) up to MAX */
declare i fixed;
S(1) = 1; S(2) = 1;
do i=2 to MAX/2;
S(i*2-1) = S(i) + S(i-1);
S(i*2) = S(i);
end;

/* print first 15 elements */
put skip list('First 15 elements: ');
do i=1 to 15;
put edit(S(i)) (F(2));
end;

/* find first occurrences of 1..10 and 100 */
do i=1 to 10;
put skip list('First',i,'at',findFirst(i));
end;
put skip list('First   ',100,'at',findFirst(100));

/* check GCDs of adjacent pairs up to 1000th element */
do i=2 to 1000;
if gcd(S(i-1),S(i)) ^= 1 then do;
put skip list('GCD of adjacent pair not 1 at i=',i);
stop;
end;
end;
put skip list('All GCDs of adjacent pairs are 1.');
end sternBrocot;```
Output:
```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 adjacent pairs are 1.```

PL/M

```100H:
/* FIND LOCATION OF FIRST ELEMENT IN ARRAY */
DECLARE (ARR, N) ADDRESS, (EL, A BASED ARR) BYTE;
N = 0;
LOOP:
IF A(N) = EL THEN RETURN N;
ELSE N = N + 1;
GO TO LOOP;
END FIND\$FIRST;

/* CP/M CALL */
BDOS: PROCEDURE (FN, ARG);
GO TO 5;
END BDOS;

PRINT: PROCEDURE (STRING);
CALL BDOS(9, STRING);
END PRINT;

/* PRINT NUMBER */
PRINT\$NUMBER: PROCEDURE (N);
DECLARE S (6) BYTE INITIAL ('.....\$');
DECLARE (N, P) ADDRESS, C BASED P BYTE;
P = .S(5);
DIGIT:
P = P - 1;
C = N MOD 10 + '0';
IF (N := N / 10) > 0 THEN GO TO DIGIT;
CALL PRINT(P);
END PRINT\$NUMBER;

/* GENERATE FIRST 1200 ELEMENTS OF STERN-BROCOT SEQUENCE */
DECLARE S (1201) BYTE, I ADDRESS;
S(1) = 1;
S(2) = 1;
DO I = 2 TO 600;
S(I*2-1) = S(I) + S(I-1);
S(I*2) = S(I);
END;

/* PRINT FIRST 15 ELEMENTS */
CALL PRINT(.'FIRST 15 ELEMENTS: \$');
DO I = 1 TO 15;
CALL PRINT\$NUMBER(S(I));
CALL PRINT(.' \$');
END;
CALL PRINT(.(13,10,'\$'));

/* PRINT FIRST OCCURRENCE OF N */
PRINT\$FIRST: PROCEDURE (N);
DECLARE N BYTE;
CALL PRINT(.'FIRST \$');
CALL PRINT\$NUMBER(N);
CALL PRINT(.' AT \$');
CALL PRINT\$NUMBER(FIND\$FIRST(.S, N));
CALL PRINT(.(13,10,'\$'));
END PRINT\$FIRST;

DO I = 1 TO 10;
CALL PRINT\$FIRST(I);
END;
CALL PRINT\$FIRST(100);

/* CHECK GCDS */
GCD: PROCEDURE (A, B) BYTE;
DECLARE (A, B, C) BYTE;
LOOP:
C = A;
A = B;
B = C MOD A;
IF B <> 0 THEN GO TO LOOP;
RETURN A;
END GCD;

DO I = 2 TO 1000;
IF GCD(S(I-1),S(I)) <> 1 THEN DO;
CALL PRINT(.'GCD NOT 1 AT: \$');
CALL PRINT\$NUMBER(I);
CALL BDOS(0,0);
END;
END;

CALL PRINT(.'ALL GCDS ARE 1\$');
CALL BDOS(0,0);
EOF```
Output:
```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 ARE 1```

PowerShell

```# An iterative approach
function iter_sb(\$count = 2000)
{
# Taken from RosettaCode GCD challenge
function Get-GCD (\$x, \$y)
{
if (\$y -eq 0) { \$x } else { Get-GCD \$y (\$x%\$y) }
}

\$index = 1
{
\$index++
}

1..10 | foreach {'Index of {0}: {1}' -f \$_, (\$answer.IndexOf(\$_) + 1)}

'Index of 100: {0}' -f (\$answer.IndexOf(100) + 1)

[bool] \$gcd = \$true
1..999 | foreach {\$gcd = \$gcd -and ((Get-GCD \$answer[\$_] \$answer[\$_ - 1]) -eq 1)}
'GCD = 1 for first 1000 members: {0}' -f \$gcd
}
```
Output:
```PS C:\> iter_sb
1
1
2
1
3
2
3
1
4
3
5
2
5
3
4
Index of 1: 1
Index of 2: 3
Index of 3: 5
Index of 4: 9
Index of 5: 11
Index of 6: 33
Index of 7: 19
Index of 8: 21
Index of 9: 35
Index of 10: 39
Index of 100: 1179
GCD = 1 for first 1000 members: True
```

PureBasic

```EnableExplicit
Define.i i

If OpenConsole("")
PrintN("Stern-Brocot_sequence")
Else
End 1
EndIf

Procedure.i f(n.i)
If n<2
ProcedureReturn n
ElseIf n&1
ProcedureReturn f(n/2)+f(n/2+1)
Else
ProcedureReturn f(n/2)
EndIf
EndProcedure

Procedure.i gcd(a.i,b.i)
If b : ProcedureReturn gcd(b,a%b) : EndIf
ProcedureReturn a
EndProcedure

Procedure.i ind(m.i)
Define.i i=1
While f(i)<>m : i+1 : Wend
ProcedureReturn i
EndProcedure

Print("First 15 elements: ")
For i=1 To 15
Print(Str(f(i))+Space(3))
Next
PrintN(~"\n")

For i=1 To 10
PrintN(RSet(Str(i),3)+" is at pos. #"+Str(ind(i)))
Next
PrintN("100 is at pos. #"+Str(ind(100)))
PrintN("")

i=1
While i<1000 And gcd(f(i),f(i+1))=1 : i+1 : Wend
If i=1000
PrintN("All GCDs are 1.")
Else
PrintN("GCD of "+Str(i)+" and "+Str(i+1)+" is not 1")
EndIf

Input()
```
Output:
```Stern-Brocot_sequence
First 15 elements: 1   1   2   1   3   2   3   1   4   3   5   2   5   3   4

1 is at pos. #1
2 is at pos. #3
3 is at pos. #5
4 is at pos. #9
5 is at pos. #11
6 is at pos. #33
7 is at pos. #19
8 is at pos. #21
9 is at pos. #35
10 is at pos. #39
100 is at pos. #1179

All GCDs are 1.```

Python

Python: procedural

```def stern_brocot(predicate=lambda series: len(series) < 20):
"""\
Generates members of the stern-brocot series, in order, returning them when the predicate becomes false

>>> print('The first 10 values:',
stern_brocot(lambda series: len(series) < 10)[:10])
The first 10 values: [1, 1, 2, 1, 3, 2, 3, 1, 4, 3]
>>>
"""

sb, i = [1, 1], 0
while predicate(sb):
sb += [sum(sb[i:i + 2]), sb[i + 1]]
i += 1
return sb

if __name__ == '__main__':
from fractions import gcd

n_first = 15
print('The first %i values:\n  ' % n_first,
stern_brocot(lambda series: len(series) < n_first)[:n_first])
print()
n_max = 10
for n_occur in list(range(1, n_max + 1)) + [100]:
print('1-based index of the first occurrence of %3i in the series:' % n_occur,
stern_brocot(lambda series: n_occur not in series).index(n_occur) + 1)
# The following would be much faster. Note that new values always occur at odd indices
# len(stern_brocot(lambda series: n_occur != series[-2])) - 1)

print()
n_gcd = 1000
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'
```
Output:
```The first 15 values:
[1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]

1-based index of the first occurrence of   1 in the series: 1
1-based index of the first occurrence of   2 in the series: 3
1-based index of the first occurrence of   3 in the series: 5
1-based index of the first occurrence of   4 in the series: 9
1-based index of the first occurrence of   5 in the series: 11
1-based index of the first occurrence of   6 in the series: 33
1-based index of the first occurrence of   7 in the series: 19
1-based index of the first occurrence of   8 in the series: 21
1-based index of the first occurrence of   9 in the series: 35
1-based index of the first occurrence of  10 in the series: 39
1-based index of the first occurrence of 100 in the series: 1179```

Python: More functional

An iterator is used to produce successive members of the sequence. (its sb variable stores less compared to the procedural version above by popping the last element every time around the while loop.
In checking the gcd's, two iterators are tee'd off from the one stream with the second advanced by one value with its call to next().

See the talk page for how a deque was selected over the use of a straightforward list'

```>>> from itertools import takewhile, tee, islice
>>>  from collections import deque
>>> from fractions import gcd
>>>
>>> def stern_brocot():
sb = deque([1, 1])
while True:
sb += [sb[0] + sb[1], sb[1]]
yield sb.popleft()

>>> [s for _, s in zip(range(15), stern_brocot())]
[1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]
>>> [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot()))
for occur in (list(range(1, 11)) + [100])]
[1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 1179]
>>> prev, this = tee(stern_brocot(), 2)
>>> next(this)
1
>>> all(gcd(p, t) == 1 for p, t in islice(zip(prev, this), 1000))
True
>>>
```

Python: Composing pure (curried) functions

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 version 3.7
```'''Stern-Brocot sequence'''

import math
import operator
from itertools import count, dropwhile, islice, takewhile

# sternBrocot :: Generator [Int]
def sternBrocot():
'''Non-finite list of the Stern-Brocot
sequence of integers.
'''
def go(xs):
[a, b] = xs[:2]
return (a, xs[1:] + [a + b, b])
return unfoldr(go)([1, 1])

# ------------------------ TESTS -------------------------
# main :: IO ()
def main():
'''Various tests'''

[eq, ne, gcd] = map(
curry,
[operator.eq, operator.ne, math.gcd]
)

sbs = take(1200)(sternBrocot())
ixSB = zip(sbs, enumFrom(1))

print(unlines(map(str, [

# First 15 members of the sequence.
take(15)(sbs),

# Indices of where the numbers [1..10] first appear.
take(10)(
nubBy(on(eq)(fst))(
sorted(
takewhile(
compose(ne(12))(fst),
ixSB
),
key=fst
)
)
),

#  Index of where the number 100 first appears.
take(1)(dropwhile(compose(ne(100))(fst), ixSB)),

# Is the gcd of any two consecutive members,
# up to the 1000th member, always one ?
every(compose(eq(1)(gcd)))(
take(1000)(zip(sbs, tail(sbs)))
)
])))

# ----------------- GENERIC ABSTRACTIONS -----------------

# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
def compose(g):
'''Right to left function composition.'''
return lambda f: lambda x: g(f(x))

# curry :: ((a, b) -> c) -> a -> b -> c
def curry(f):
'''A curried function derived
from an uncurried function.'''
return lambda a: lambda b: f(a, b)

# enumFrom :: Enum a => a -> [a]
def enumFrom(x):
'''A non-finite stream of enumerable values,
starting from the given value.'''
return count(x) if isinstance(x, int) else (
map(chr, count(ord(x)))
)

# every :: (a -> Bool) -> [a] -> Bool
def every(p):
'''True if p(x) holds for every x in xs'''
return lambda xs: all(map(p, xs))

# fst :: (a, b) -> a
def fst(tpl):
'''First member of a pair.'''
return tpl[0]

# head :: [a] -> a
'''The first element of a non-empty list.'''
return xs[0]

# nubBy :: (a -> a -> Bool) -> [a] -> [a]
def nubBy(p):
'''A sublist of xs from which all duplicates,
(as defined by the equality predicate p)
are excluded.
'''
def go(xs):
if not xs:
return []
x = xs[0]
return [x] + go(
list(filter(
lambda y: not p(x)(y),
xs[1:]
))
)
return go

# on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
def on(f):
'''A function returning the value of applying
the binary f to g(a) g(b)'''
return lambda g: lambda a: lambda b: f(g(a))(g(b))

# tail :: [a] -> [a]
# tail :: Gen [a] -> [a]
def tail(xs):
'''The elements following the head of a
(non-empty) list or generator stream.'''
if isinstance(xs, list):
return xs[1:]
else:
islice(xs, 1)  # First item dropped.
return xs

# take :: Int -> [a] -> [a]
# take :: Int -> String -> String
def take(n):
'''The prefix of xs of length n,
or xs itself if n > length xs.'''
return lambda xs: (
xs[0:n]
if isinstance(xs, list)
else list(islice(xs, n))
)

# unfoldr :: (b -> Maybe (a, b)) -> b -> Gen [a]
def unfoldr(f):
'''A lazy (generator) list unfolded from a seed value
by repeated application of f until no residue remains.
Dual to fold/reduce.
f returns either None or just (value, residue).
For a strict output list, wrap the result with list()
'''
def go(x):
valueResidue = f(x)
while valueResidue:
yield valueResidue[0]
valueResidue = f(valueResidue[1])
return go

# unlines :: [String] -> String
def unlines(xs):
'''A single string derived by the intercalation
of a list of strings with the newline character.'''
return '\n'.join(xs)

# MAIN ---
if __name__ == '__main__':
main()
```
Output:
```[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```

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
[ tuck gcd 1 != if
[ dip not conclude ] ]
drop iff
[ say "Reducible pair found." ]
else
[ say "No reducible pairs found." ]```
Output:
```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.
```

R

For loop

Translation of: PARI/GP
Works with: R version 3.3.2 and above
Library: pracma
```## Stern-Brocot sequence
## 12/19/16 aev
SternBrocot <- function(n){
V <- 1; k <- n/2;
for (i in 1:k)
{ V[2*i] = V[i]; V[2*i+1] = V[i] + V[i+1];}
return(V);
}

## Required tests:
require(pracma);
{
cat(" *** The first 15:",SternBrocot(15),"\n");
cat(" *** The first i@n:","\n");
V=SternBrocot(40);
for (i in 1:10) {j=match(i,V); cat(i,"@",j,",")}
V=SternBrocot(1200);
i=100; j=match(i,V); cat(i,"@",j,"\n");
V=SternBrocot(1000); j=1;
for (i in 2:1000) {j=j*gcd(V[i-1],V[i])}
if(j==1) {cat(" *** All GCDs=1!\n")} else {cat(" *** All GCDs!=1??\n")}
}
```
Output:
```> require(pracma)
*** The first 15: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
*** The first i@n:
1 @ 1 ,2 @ 3 ,3 @ 5 ,4 @ 9 ,5 @ 11 ,6 @ 33 ,7 @ 19 ,8 @ 21 ,9 @ 35 ,10 @ 39 ,100 @ 1179
*** All GCDs=1!
>
```

While loop

Library: gmp

Tasks like this are R's bread and butter. The previous solution uses smart mathematical tricks to generate the desired sequence with a for loop and uses a similarly clever for loop for the task involving gcds. However, R is smart enough to let us avoid this work by writing some much more idiomatic code.

As with the previous solution, we have used a library for our gcd function. In this case, we have used gmp.

```genNStern <- function(n)
{
sternNums <- c(1, 1)
i <- 2
while((endIndex <- length(sternNums)) < n)
{
#To show off R's vectorization, the following line is deliberately terse.
#It assigns sternNums[i-1]+sternNums[i] to sternNums[endIndex+1]
#and it assigns sternNums[i], the "considered" number, to sternNums[endIndex+2], now the end of the sequence.
#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[seq_len(n)]
}
#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:
```> 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```

Racket

```#lang racket
;; OEIS Definition
;; A002487
;;   Stern's diatomic series
;;   (or Stern-Brocot sequence):
;;     a(0) = 0, a(1) = 1;
;;     for n > 0:
;;       a(2*n) = a(n),
;;       a(2*n+1) = a(n) + a(n+1).
(define A002487
(let ((memo (make-hash '((0 . 0) (1 . 1)))))
(lambda (n)
(hash-ref! memo n
(lambda ()
(define n/2 (quotient n 2))
(+ (A002487 n/2) (if (even? n) 0 (A002487 (add1 n/2)))))))))

(define Stern-Brocot A002487)

(displayln "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)")
(for/list ((i (in-range 1 (add1 15)))) (Stern-Brocot i))

(displayln "Show the (1-based) index of where the numbers 1-to-10 first appears in the sequence.")
(for ((n (in-range 1 (add1 10))))
(for/first ((i (in-naturals 1))
#:when (= n (Stern-Brocot i)))
(printf "~a first found at a(~a)~%" n i)))

(displayln "Show the (1-based) index of where the number 100 first appears in the sequence.")
(for/first ((i (in-naturals 1)) #:when (= 100 (Stern-Brocot i))) i)

(displayln "Check that the greatest common divisor of all the two consecutive members of the
series up to the 1000th member, is always one.")
(unless
(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"))
```
Output:
```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)
(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 first appears in the sequence.
1 first found at a(1)
2 first found at a(3)
3 first found at a(5)
4 first found at a(9)
5 first found at a(11)
6 first found at a(33)
7 first found at a(19)
8 first found at a(21)
9 first found at a(35)
10 first found at a(39)
Show the (1-based) index of where the number 100 first appears in the sequence.
1179
Check that the greatest common divisor of all the two consecutive members of the
series up to the 1000th member, is always one.
didn't find gcd > (or otherwise ≠) 1```

Raku

(formerly Perl 6)

Works with: rakudo version 2017-03
```constant @Stern-Brocot = 1, 1, { |(@_[\$_ - 1] + @_[\$_], @_[\$_]) given ++\$ } ... *;

put @Stern-Brocot[^15];

for flat 1..10, 100 -> \$ix {
say "First occurrence of {\$ix.fmt('%3d')} is at index: {(1+@Stern-Brocot.first(\$ix, :k)).fmt('%4d')}";
}

say so 1 == all map ^1000: { [gcd] @Stern-Brocot[\$_, \$_ + 1] }
```
Output:
```1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
First occurrence of   1 is at index:    1
First occurrence of   2 is at index:    3
First occurrence of   3 is at index:    5
First occurrence of   4 is at index:    9
First occurrence of   5 is at index:   11
First occurrence of   6 is at index:   33
First occurrence of   7 is at index:   19
First occurrence of   8 is at index:   21
First occurrence of   9 is at index:   35
First occurrence of  10 is at index:   39
First occurrence of 100 is at index: 1179
True```

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.';
};```
Output:
```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.```

REXX

```/*REXX program generates & displays a Stern─Brocot sequence; finds 1─based indices; GCDs*/
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.*/
if idx=='' | idx==","  then idx=   10            /* "      "         "   "   "     "    */
if fix=='' | fix==","  then fix=  100            /* "      "         "   "   "     "    */
if chk=='' | chk==","  then chk= 1000            /* "      "         "   "   "     "    */

if N>0  then say center('the first'   N   "numbers in the Stern─Brocot sequence", 70, '═')
a= Stern_Brocot(N)                               /*invoke function to generate sequence.*/
say a                                            /*display the sequence to the terminal.*/
say
say center('the 1─based index for the first'       idx        "integers",   70, '═')
a= Stern_Brocot(-idx)                            /*invoke function to generate sequence.*/
w= length(idx);        do i=1  for idx
say 'for '   right(i, w)",  the index is: "          wordpos(i, a)
end   /*i*/
say
say center('the 1─based index for'  fix, 70, "═")
a= Stern_Brocot(-fix)                            /*invoke function to generate sequence.*/
say 'for '       fix",  the index is: "      wordpos(fix, a)
say
if chk<2  then exit 0
say center('checking if all two consecutive members have a GCD=1', 70, '═')
a= Stern_Brocot(chk)                             /*invoke function to generate sequence.*/
do c=1  for chk-1;    if gcd(subword(a, c, 2))==1  then iterate
say 'GCD check failed at index'         c;         exit 13
end   /*c*/
say
say '───── All '     chk     " two consecutive members have a GCD of unity."
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
gcd: procedure; \$=;     do i=1  for arg();     \$= \$ arg(i)              /*get arg list. */
end   /*i*/
parse var \$ x z .;                if x=0  then x= z                /*is zero case? */
x=abs(x)                                                           /*use absolute x*/
do j=2  to words(\$);    y=abs( word(\$, j) )
if y=0  then iterate                                     /*ignore zeros. */
do  until y==0;      parse value x//y y  with  y x    /* ◄──heavy work*/
end   /*until*/
end      /*j*/
return x                                                           /*return the GCD*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
Stern_Brocot:  parse arg h 1 f;                \$= 1 1;           if h<0  then h= 1e9
else f= 0
f= abs(f)
do k=2  until words(\$)>=h  |  wordpos(f, \$)\==0
_= word(\$, k);      \$= \$   (_ + word(\$, k-1) )   _
end   /*k*/
if f==0  then return subword(\$, 1, h)
return \$
```
output   when using the default inputs:
```══════════the first 15 numbers in the Stern─Brocot sequence═══════════
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4

═════════════the 1-based index for the first 10 integers══════════════
for   1,  the index is:  1
for   2,  the index is:  3
for   3,  the index is:  5
for   4,  the index is:  9
for   5,  the index is:  11
for   6,  the index is:  33
for   7,  the index is:  19
for   8,  the index is:  21
for   9,  the index is:  35
for  10,  the index is:  39

══════════════════════the 1-based index for 100═══════════════════════
for  100,  the index is:  1179

═════════checking if all two consecutive members have a GCD=1═════════
───── All  1000  two consecutive members have a GCD of unity.
```

Ring

```# Project : Stern-Brocot sequence

limit = 1200
item = list(limit+1)
item[1] = 1
item[2] = 1
nr = 2
gcd = 1
gcdall = 1
for num = 3 to limit
item[num] = item[nr] + item[nr-1]
item[num+1] = item[nr]
nr = nr + 1
num = num + 1
next
showarray(item,15)

for x = 1 to 100
if x < 11 or x = 100
totalitem(x)
ok
next

for n = 1 to len(item) - 1
if gcd(item[n],item[n+1]) != 1
gcdall = gcd
ok
next

if gcdall = 1
see "Correct: The first 999 consecutive pairs are relative prime!" + nl
ok

func totalitem(p)
pos = find(item, p)
see string(x) + " at Stern #" + pos + "." + nl

func showarray(vect,ln)
svect = ""
for n = 1 to ln
svect = svect + vect[n] + ", "
next
svect = left(svect, len(svect) - 2)
see svect
see nl

func gcd(gcd,b)
while b
c = gcd
gcd = b
b = c % b
end
return gcd```

Output:

```1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4
1 at Stern #1.
2 at Stern #3.
3 at Stern #5.
4 at Stern #9.
5 at Stern #11.
6 at Stern #33.
7 at Stern #19.
8 at Stern #21.
9 at Stern #35.
10 at Stern #39.
100 at Stern #1179.
Correct: The first 999 consecutive pairs are relative prime!
```

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 version 4.2.7
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

≪
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)
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

```
Input:
```15 TASK1
{ } 1 10 FOR n n WHEN + NEXT
100 WHEN
```
Output:
```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)
```

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).

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
```

Ruby

Works with: Ruby version 2.1
```def sb
return enum_for :sb unless block_given?
a=[1,1]
0.step do |i|
yield a[i]
a << a[i]+a[i+1] << a[i+1]
end
end

puts "First 15: #{sb.first(15)}"

[*1..10,100].each do |n|
puts "#{n} first appears at #{sb.find_index(n)+1}."
end

if sb.take(1000).each_cons(2).all? { |a,b| a.gcd(b) == 1 }
puts "All GCD's are 1"
else
puts "Whoops, not all GCD's are 1!"
end
```
Output:
```First 15: [1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]
1 first appears at 1.
2 first appears at 3.
3 first appears at 5.
4 first appears at 9.
5 first appears at 11.
6 first appears at 33.
7 first appears at 19.
8 first appears at 21.
9 first appears at 35.
10 first appears at 39.
100 first appears at 1179.
All GCD's are 1
```

Scala

```lazy val sbSeq: Stream[BigInt] = {
BigInt("1") #::
BigInt("1") #::
(sbSeq zip sbSeq.tail zip sbSeq.tail).
flatMap{ case ((a,b),c) => List(a+b,c) }
}

// Show the results
{
println( s"First 15 members: \${(for( n <- 0 until 15 ) yield sbSeq(n)) mkString( "," )}" )
println
for( n <- 1 to 10; pos = sbSeq.indexOf(n) + 1 ) println( s"Position of first \$n is at \$pos" )
println
println( s"Position of first 100 is at \${sbSeq.indexOf(100) + 1}" )
println
println( s"Greatest Common Divisor for first 1000 members is 1: " +
(sbSeq zip sbSeq.tail).take(1000).forall{ case (a,b) => a.gcd(b) == 1 } )
}
```
Output:
```First 15 members: 1,1,2,1,3,2,3,1,4,3,5,2,5,3,4

Position of first 1 is at 1
Position of first 2 is at 3
Position of first 3 is at 5
Position of first 4 is at 9
Position of first 5 is at 11
Position of first 6 is at 33
Position of first 7 is at 19
Position of first 8 is at 21
Position of first 9 is at 35
Position of first 10 is at 39

Position of first 100 is at 1179

Greatest Common Divisor for first 1000 members is 1: true
```

Scheme

Works with: Chez Scheme

The Function

```; 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))))))))
```

```; 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.

(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)
(printf "GCDs of all Stern-Brocot consecutive pairs from 1 to 1000 are 1~%")))
```
Output:
```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```

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;```
Output:
```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.```

Sidef

Translation of: Perl
```# Declare a function to generate the Stern-Brocot sequence
func stern_brocot {
var list = [1, 1]
{
list.append(list[0]+list[1], list[1])
list.shift
}
}

# Show the first fifteen members of the sequence.
say 15.of(stern_brocot()).join(' ')

# Show the (1-based) index of where the numbers 1-to-10 first appears
# in the sequence, and where the number 100 first appears in the sequence.
for i (1..10, 100) {
var index = 1
var generator = stern_brocot()
while (generator() != i) {
++index
}
say "First occurrence of #{i} is at index #{index}"
}

# Check that the greatest common divisor of all the two consecutive
# members of the series up to the 1000th member, is always one.
var generator = stern_brocot()
var (a, b) = (generator(), generator())
{
assert_eq(gcd(a, b), 1)
a = b
b = generator()
} * 1000

say "All GCD's are 1"
```
Output:
```1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
First occurrence of 1 is at index 1
First occurrence of 2 is at index 3
First occurrence of 3 is at index 5
First occurrence of 4 is at index 9
First occurrence of 5 is at index 11
First occurrence of 6 is at index 33
First occurrence of 7 is at index 19
First occurrence of 8 is at index 21
First occurrence of 9 is at index 35
First occurrence of 10 is at index 39
First occurrence of 100 is at index 1179
All GCD's are 1
```

Snobol

```*       GCD function
DEFINE('GCD(A,B)')                      :(GCD_END)
GCD     GCD = A
EQ(B,0)                                 :S(RETURN)
A = B
B = REMDR(GCD,B)                        :(GCD)
GCD_END

*       Find first occurrence of element in array
DEFINE('IDX(ARR,ELM)')                  :(IDX_END)
IDX     IDX = 1
ITEST   EQ(ARR<IDX>,ELM)                        :S(RETURN)
IDX = IDX + 1                           :(ITEST)
IDX_END

*       Declare array
SEQ = ARRAY(1200,1)

*       Fill array with Stern-Brocot sequence
IX = 1
FILL    IX = IX + 1
SEQ<IX * 2 - 1> = SEQ<IX> + SEQ<IX - 1>
SEQ<IX * 2> = SEQ<IX>                   :S(FILL)

*       Print first 15 elements
DONE    IX = 1
S = "First 15 elements:"
P15     S = S " " SEQ<IX>
IX = IX + 1 LT(IX,15)                   :S(P15)
OUTPUT = S

*       Print first occurrence of 1..10 and 100
N = 1
FIRSTN  OUTPUT = "First " N " at " IDX(SEQ,N)
N = N + 1 LT(N,10)                      :S(FIRSTN)
OUTPUT = "First 100 at " IDX(SEQ,100)

*       Test GCD between 1000 consecutive members
IX = 2
GCDTEST EQ(GCD(SEQ<IX - 1>,SEQ<IX>),1)          :F(GCDFAIL)
IX = IX + 1 LT(IX,1000)                 :S(GCDTEST)
OUTPUT = "All GCDs are 1."              :(END)
GCDFAIL OUTPUT = "GCD is not 1 at " IX "."

END
```
Output:
```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 are 1.```

Swift

```struct SternBrocot: Sequence, IteratorProtocol {
private var seq = [1, 1]

mutating func next() -> Int? {
seq += [seq[0] + seq[1], seq[1]]

return seq.removeFirst()
}
}

func gcd<T: BinaryInteger>(_ a: T, _ b: T) -> T {
guard a != 0 else {
return b
}

return a < b ? gcd(b % a, a) : gcd(a % b, b)
}

print("First 15: \(Array(SternBrocot().prefix(15)))")

var found = Set<Int>()

for (i, val) in SternBrocot().enumerated() {
switch val {
case 1...10 where !found.contains(val), 100 where !found.contains(val):
print("First \(val) at \(i + 1)")
found.insert(val)
case _:
continue
}

if found.count == 11 {
break
}
}

let firstThousand = SternBrocot().prefix(1000)
let gcdIsOne = zip(firstThousand, firstThousand.dropFirst()).allSatisfy({ gcd(\$0.0, \$0.1) == 1 })

print("GCDs of all two consecutive members are \(gcdIsOne ? "" : "not")one")
```
Output:
```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 7 at 19
First 8 at 21
First 6 at 33
First 9 at 35
First 10 at 39
First 100 at 1179
GCDs of all two consecutive members are one```

Tcl

```#!/usr/bin/env tclsh
#

package require generator   ;# from tcllib

namespace eval stern-brocot {
proc generate {{count 100}} {
set seq {1 1}
set n 0
while {[llength \$seq] < \$count} {
lassign [lrange \$seq \$n \$n+1] a b
lappend seq [expr {\$a + \$b}] \$b
incr n
}
return \$seq
}

proc genr {} {
yield [info coroutine]
set seq {1 1}
while {1} {
set seq [lassign \$seq a]
set b [lindex \$seq 0]
set c [expr {\$a + \$b}]
lappend seq \$c \$b
yield \$a
}
}

proc Step {a b args} {
set c [expr {\$a + \$b}]
list \$a [list \$b {*}\$args \$c \$b]
}

generator define gen {} {
set cmd [list 1 1]
while {1} {
lassign [Step {*}\$cmd] a cmd
generator yield \$a
}
}

namespace export {[a-z]*}
namespace ensemble create
}

interp alias {} sb {} stern-brocot

# a simple adaptation of gcd from http://wiki.tcl.tk/2891
proc coprime {a args} {
set gcd \$a
foreach arg \$args {
while {\$arg != 0} {
set t \$arg
set arg [expr {\$gcd % \$arg}]
set gcd \$t
if {\$gcd == 1} {return true}
}
}
return false
}

proc main {} {

puts "#1. First 15 members of the Stern-Brocot sequence:"
puts \t[generator to list [generator take 16 [sb gen]]]

puts "#2. First occurrences of 1 through 10:"
set first {}
set got 0
set i 0
generator foreach x [sb gen] {
incr i
if {\$x>10} continue
if {[dict exists \$first \$x]} continue
dict set first \$x \$i
if {[incr got] >= 10} break
}
foreach {a b} [lsort -integer -stride 2 \$first] {
puts "\tFirst \$a at \$b"
}

puts "#3. First occurrence of 100:"
set i 0
generator foreach x [sb gen] {
incr i
if {\$x eq 100} break
}
puts "\tFirst \$x at \$i"

puts "#4. Check first 1k elements for common divisors:"
set prev [expr {2*3*5*7*11*13*17*19+1}] ;# a handy prime
set i 0
generator foreach x [sb gen] {
if {[incr i] >= 1000} break
if {![coprime \$x \$prev]} {
error "Element \$i, \$x is not coprime with \$prev!"
}
set prev \$x
}
puts "\tFirst \$i elements are all pairwise coprime"
}

main
```
Output:
```#1. First 15 members of the Stern-Brocot sequence:
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4
#2. First occurrences of 1 through 10:
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
#3. First occurrence of 100:
First 100 at 1179
#4. Check first 1k elements for common divisors:
First 1000 elements are all pairwise coprime
```

VBScript

```sb = Array(1,1)
i = 1 'considered
j = 2 'precedent
n = 0 'loop counter
Do
ReDim Preserve sb(UBound(sb) + 1)
sb(UBound(sb)) = sb(UBound(sb) - i) + sb(UBound(sb) - j)
ReDim Preserve sb(UBound(sb) + 1)
sb(UBound(sb)) = sb(UBound(sb) - j)
i = i + 1
j = j + 1
n = n + 1
Loop Until n = 2000

WScript.Echo "First 15: " & DisplayElements(15)

For k = 1 To 10
WScript.Echo "The first instance of " & k & " is in #" & ShowFirstInstance(k) & "."
Next

WScript.Echo "The first instance of " & 100 & " is in #" & ShowFirstInstance(100) & "."

Function DisplayElements(n)
For i = 0 To n - 1
If i < n - 1 Then
DisplayElements = DisplayElements & sb(i) & ", "
Else
DisplayElements = DisplayElements & sb(i)
End If
Next
End Function

Function ShowFirstInstance(n)
For i = 0 To UBound(sb)
If sb(i) = n Then
ShowFirstInstance = i + 1
Exit For
End If
Next
End Function
```
Output:
```First 15: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4
The first instance of 1 is in #1.
The first instance of 2 is in #3.
The first instance of 3 is in #5.
The first instance of 4 is in #9.
The first instance of 5 is in #11.
The first instance of 6 is in #33.
The first instance of 7 is in #19.
The first instance of 8 is in #21.
The first instance of 9 is in #35.
The first instance of 10 is in #39.
The first instance of 100 is in #1179.```

Visual Basic .NET

Translation of: C#
```Imports System
Imports System.Collections.Generic
Imports System.Linq

Module Module1
Dim l As List(Of Integer) = {1, 1}.ToList()

Function gcd(ByVal a As Integer, ByVal b As Integer) As Integer
Return If(a > 0, If(a < b, gcd(b Mod a, a), gcd(a Mod b, b)), b)
End Function

Sub Main(ByVal args As String())
Dim max As Integer = 1000, take As Integer = 15, i As Integer = 1,
selection As Integer() = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100}
Do : l.AddRange({l(i) + l(i - 1), l(i)}.ToList) : i += 1
Loop While l.Count < max OrElse l(l.Count - 2) <> selection.Last()
Console.Write("The first {0} items In the Stern-Brocot sequence: ", take)
Console.WriteLine("{0}" & vbLf, String.Join(", ", l.Take(take)))
Console.WriteLine("The locations of where the selected numbers (1-to-10, & 100) first appear:")
For Each ii As Integer In selection
Dim j As Integer = l.FindIndex(Function(x) x = ii) + 1
Console.WriteLine("{0,3}: {1:n0}", ii, j)
Next : Console.WriteLine() : Dim good As Boolean = True : For i = 1 To max
If gcd(l(i), l(i - 1)) <> 1 Then good = False : Exit For
Next
Console.WriteLine("The greatest common divisor of all the two consecutive items of the" &
" series up to the {0}th item is {1}always one.", max, If(good, "", "not "))
End Sub
End Module
```
Output:
```The first 15 items In the Stern-Brocot sequence: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4

The locations of where the selected numbers (1-to-10, & 100) first appear:
1: 1
2: 3
3: 5
4: 9
5: 11
6: 33
7: 19
8: 21
9: 35
10: 39
100: 1,179

The greatest common divisor of all the two consecutive items of the series up to the 1000th item is always one.
```

Wren

Translation of: Kotlin
Library: Wren-math
Library: Wren-fmt
```import "./math" for Int
import "./fmt" for Fmt

var sbs = [1, 1]

var sternBrocot = Fn.new { |n, fromStart|
if (n < 4 || (n % 2 != 0)) Fiber.abort("n must be >= 4 and even.")
var consider = fromStart ? 1 : (n/2).floor - 1
while (true) {
var sum = sbs[consider] + sbs[consider - 1]
if (sbs.count == n) return
consider = consider + 1
}
}

var n = 16  // needs to be even to ensure 'considered' number is added
System.print("First 15 members of the Stern-Brocot sequence:")
sternBrocot.call(n, true)
System.print(sbs.take(15).toList)

var firstFind = List.filled(11, 0)
firstFind[0] = -1 // needs to be non-zero for subsequent test
var i = 0
for (v in sbs) {
if (v <= 10 && firstFind[v] == 0) firstFind[v] = i + 1
i = i + 1
}
while (true) {
n = n + 2
sternBrocot.call(n, false)
var vv = sbs[-2..-1]
var m = n - 1
var outer = false
for (v in vv) {
if (v <= 10 && firstFind[v] == 0) firstFind[v] = m
if (firstFind.all { |e| e != 0 }) {
outer = true
break
}
m = m + 1
}
if (outer) break
}
System.print("\nThe numbers 1 to 10 first appear at the following indices:")
for (i in 1..10) Fmt.print("\$2d -> \$d", i, firstFind[i])

System.write("\n100 first appears at index ")
while (true) {
n = n + 2
sternBrocot.call(n, false)
var vv = sbs[-2..-1]
if (vv[0] == 100) {
System.print("%(n - 1).")
break
}
if (vv[1] == 100) {
System.print("%(n).")
break
}
}

System.write("\nThe GCDs of each pair of the series up to the 1,000th member are ")
var p = 0
while (p < 1000) {
if (Int.gcd(sbs[p], sbs[p + 1]) != 1) {
System.print("not all one.")
return
}
p = p + 2
}
System.print("all one.")
```
Output:
```First 15 members of the Stern-Brocot sequence:
[1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]

The numbers 1 to 10 first appear at the following indices:
1 -> 1
2 -> 3
3 -> 5
4 -> 9
5 -> 11
6 -> 33
7 -> 19
8 -> 21
9 -> 35
10 -> 39

100 first appears at index 1179.

The GCDs of each pair of the series up to the 1,000th member are all one.
```

zkl

```fcn SB  // Stern-Brocot sequence factory --> Walker
{ Walker(fcn(sb,n){ a,b:=sb; sb.append(a+b,b); sb.del(0); a }.fp(L(1,1))) }

SB().walk(15).println();

[1..10].zipWith('wrap(n){ [1..].zip(SB())
.filter(1,fcn(n,sb){ n==sb[1] }.fp(n)) })
.walk().println();
[1..].zip(SB()).filter1(fcn(sb){ 100==sb[1] }).println();

sb:=SB(); do(500){ if(sb.next().gcd(sb.next())!=1) println("Oops") }```
Output:
```L(1,1,2,1,3,2,3,1,4,3,5,2,5,3,4)
L(L(L(1,1)),L(L(3,2)),L(L(5,3)),L(L(9,4)),L(L(11,5)),L(L(33,6)),L(L(19,7)),L(L(21,8)),L(L(35,9)),L(L(39,10)))
L(1179,100)
```