# 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 appears 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

## 360 Assembly

Translation of: Fortran
`*        Stern-Brocot sequence     - 12/03/2019STERNBR  CSECT         USING  STERNBR,R13        base register         B      72(R15)            skip savearea         DC     17F'0'             savearea         SAVE   (14,12)            save previous context         ST     R13,4(R15)         link backward         ST     R15,8(R13)         link forward         LR     R13,R15            set addressability         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 counterLOOP     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 iEXITI    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               nnPG       DC     CL80' '            bufferXDEC     DS     CL12               temp for xdecoSB       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 counterLOOP     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 `

`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;    use Ada.Text_IO; 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!```

## AppleScript

`use AppleScript version "2.4"use framework "Foundation"use scripting additions  -- sternBrocot :: Generator [Int]on sternBrocot()    script go        on |λ|(xs)            set x to snd(xs)            tail(xs) & {fst(xs) + x, x}        end |λ|    end script    fmapGen(my head, iterate(go, {1, 1}))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 ABSTRACTIONS -------------------------------------------------------  -- Absolute value.-- abs :: Num -> Numon abs(x)    if 0 > x then        -x    else        x    end ifend abs -- Applied to a predicate and a list, `all` determines if all elements -- of the list satisfy the predicate.-- all :: (a -> Bool) -> [a] -> Boolon 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 tellend 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 scriptend comparing  -- drop :: Int -> [a] -> [a]-- drop :: Int -> String -> Stringon 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 ifend drop -- dropWhile :: (a -> Bool) -> [a] -> [a]-- dropWhile :: (Char -> Bool) -> String -> Stringon 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 scriptend 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 tellend 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 scriptend fmapGen -- fst :: (a, b) -> aon fst(tpl)    if class of tpl is record then        |1| of tpl    else        item 1 of tpl    end ifend fst -- gcd :: Int -> Int -> Inton 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 xend gcd -- head :: [a] -> aon head(xs)    if xs = {} then        missing value    else        item 1 of xs    end ifend head -- 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 scriptend iterate  -- length :: [a] -> Inton |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 ifend |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 tellend map  -- min :: Ord a => a -> a -> aon min(x, y)    if y < x then        y    else        x    end ifend 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 ifend 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 -> Stringon 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 ifend showJSON -- snd :: (a, b) -> bon snd(tpl)    if class of tpl is record then        |2| of tpl    else        item 2 of tpl    end ifend 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 ifend 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 ifend tail -- take :: Int -> [a] -> [a]-- take :: Int -> String -> Stringon 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 ifend take -- takeWhile :: (a -> Bool) -> [a] -> [a]-- takeWhile :: (Char -> Bool) -> String -> Stringon 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 ifend 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 ysend takeWhileGen -- Tuple (,) :: a -> b -> (a, b)on Tuple(a, b)    {type:"Tuple", |1|:a, |2|:b, length:2}end Tuple -- unlines :: [String] -> Stringon 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    strend 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 tellend 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```

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

## 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++

` #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'!
```

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

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

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

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

## 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   def task do    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 SternBrocot.task`
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., 2018let sb=Seq.unfold(fun (n::g::t)->Some(n,[g]@[email protected][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 mathmath.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 ] [email protected] 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.
```

## 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 : PrintPrint "  Index   First nr."Dim As UInteger d = 1For 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 IfNext Print : Printd = 0For i = 1 To 1000    If gcd(stern(i), stern(i +1)) <> 1 Then        d = gcd(stern(i), stern(i +1))        Exit For    End IfNext 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; " = "; dEnd If ' empty keyboard bufferWhile Inkey <> "" : WendPrint : Print "hit any key to end program"SleepEnd`
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))     // Tasks 3 and 4.    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))    }     // Task 5.    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 taskfunc 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.//// Terms are stored in a slice.  Terms start with 1.// (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.List (nubBy, sortBy)import Data.Ord (comparing)import Data.Monoid ((<>))import Data.Function (on) sternBrocot :: [Int]sternBrocot =  let go (a:b:xs) = (b : xs) <> [a + b, b]  in head <\$> iterate go [1, 1] -- TEST -------------------------------------------------------------main :: IO ()main = do  print \$ take 15 sternBrocot  print \$    take 10 \$    nubBy (on (==) fst) \$    sortBy (comparing 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```

## 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]));            };            return fmapGen(head, iterate(go, [1, 1]));        };          // 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```

## 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<:#) sternbrocot1 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.101 3 5 9 11 33 19 21 35 39`

One based index of where the number 100 first appears:

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

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

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

## 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;import java.util.LinkedList; public class SternBrocot {	static LinkedList<Integer> sequence = new LinkedList<Integer>(){{		add(1); add(1);	}}; 	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);			sequence.add(consider + pre);			sequence.add(consider);		} 	} 	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.add(new SternBrocot(), BorderLayout.CENTER);            f.pack();            f.setLocationRelativeTo(null);            f.setVisible(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 ; def index_task:  (range(1;11), 100) as \$i  | "index of \(\$i) is \(stern_brocot_index(\$i))" ; def gcd_task:  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:",index_task,"",gcd_task `
Output:
`\$ jq -r -n -f stern_brocot.jqFirst 15 integers of the Stern-Brocot sequenceas defined in the task description are:112132314352534 Using an index origin of 1:index of 1 is 1index of 2 is 3index of 3 is 5index of 4 is 9index of 5 is 11index of 6 is 33index of 7 is 19index of 8 is 21index of 9 is 35index of 10 is 39index of 100 is 1179 GCDs are all 1`

## Julia

Translation of: Python
`function sternbrocot(f::Function=(x) -> length(x) ≥ 20)::Vector{Int}    rst = Int[1, 1]    i = 3    while !f(rst)        append!(rst, Int[rst[i-1] + rst[i-2], rst[i-2]])        i += 1    end    return rstend 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, 1, 3, 2, 4, 1, 4, 3, 4, 1, 5]

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:   15
Index of first occurrence of   6 in the series:   17
Index of first occurrence of   7 in the series:   23
Index of first occurrence of   8 in the series:   31
Index of first occurrence of   9 in the series:   33
Index of first occurrence of  10 in the series:   51
Index of first occurrence of 100 in the series: 1855

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

## 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]        sbs.add(sum)        sbs.add(sbs[consider])        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 1function 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 sbListend -- 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 nilend -- 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)    endend -- Check GCD of adjacent values in 't' up to 1000 is always 1function task5 (t)    for pos = 1, 1000 do        if gcd(t[pos], t[pos + 1]) ~= 1 then return "FAIL" end    end    return "PASS"end -- Main procedurelocal sb = sternBrocot(10000)io.write("Task 2: ")for n = 1, 15 do io.write(sb[n] .. " ") endprint("\n\nTask 3:")for i = 1, 10 do print("\t" .. i, findFirst(sb, i)) endprint("\nTask 4: " .. findFirst(sb, 100)) print("\nTask 5: " .. task5(sb))`
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

## Oforth

`: stern(n)| l i |   ListBuffer new dup add(1) dup add(1) dup ->l   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 aevSternBrocot(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 aevfindinlist(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 [email protected]: "); \\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 [email protected]: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
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_Pascalvar  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.```

## Perl 6

Works with: rakudo version 2017-03
`constant @Stern-Brocot = 1, 1, {    |(@_[\$_ - 1] + @_[\$_], @_[\$_]) given ++\$} ... *; say @Stern-Brocot[^15]; for (flat 1..10, 100) -> \$ix {    say "first occurrence of \$ix is at index : ", 1 + @Stern-Brocot.first(\$ix, :k);} 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```

## 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:")?sinteger n = 16, ksequence 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] = kend forputs(1,"indexes of 1..10:")?idxputs(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?ks = stern_brocot(1000)integer maxgcd = 1for i=1 to 999 do    maxgcd = max(gcd(s[i],s[i+1]),maxgcd)end forprintf(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))   (println 'First-15: (head 15 Lst))   (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!
```

## PowerShell

` # An iterative approachfunction 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) }    }     \$answer = @(1,1)    \$index = 1    while (\$answer.Length -le \$count)    {        \$answer += \$answer[\$index] + \$answer[\$index - 1]        \$answer += \$answer[\$index]        \$index++    }     0..14 | foreach {\$answer[\$_]}     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
```

## 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''' from itertools import (count, dropwhile, islice, takewhile)import operatorimport math  # sternBrocot :: Generator [Int]def sternBrocot():    '''Non-finite list of the Stern-Brocot       sequence of integers.'''     def go(xs):        x = xs[1]        return (tail(xs) + [x + head(xs), x])    return fmapGen(head)(        iterate(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 -> cdef compose(g):    '''Right to left function composition.'''    return lambda f: lambda x: g(f(x))  # curry :: ((a, b) -> c) -> a -> b -> cdef 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] -> Booldef every(p):    '''True if p(x) holds for every x in xs'''    return lambda xs: all(map(p, xs))  # fmapGen <\$> :: (a -> b) -> Gen [a] -> Gen [b]def fmapGen(f):    '''A function f mapped over a       non finite stream of values.'''    def go(g):        while True:            v = next(g, None)            if None is not v:                yield f(v)            else:                return    return lambda gen: go(gen)  # fst :: (a, b) -> adef fst(tpl):    '''First member of a pair.'''    return tpl[0]  # head :: [a] -> adef head(xs):    '''The first element of a non-empty list.'''    return xs[0]  # iterate :: (a -> a) -> a -> Gen [a]def iterate(f):    '''An infinite list of repeated       applications of f to x.'''    def go(x):        v = x        while True:            yield v            v = f(v)    return lambda x: go(x)  # 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 lambda xs: go(xs)  # on :: (b -> b -> c) -> (a -> b) -> a -> a -> cdef 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:        list(islice(xs, 1))  # First item dropped.        return xs  # take :: Int -> [a] -> [a]# take :: Int -> String -> Stringdef 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))    )  # unlines :: [String] -> Stringdef 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```

## R

Translation of: PARI/GP
Works with: R version 3.3.2 and above
` ## Stern-Brocot sequence## 12/19/16 aevSternBrocot <- 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 [email protected]:","\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 [email protected]:
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!
>
```

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

## 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             /* "      "         "   "   "     "    */ 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.*/saysay 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*/saysay 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)saysay 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 '───── All '     chk     " two consecutive members have a GCD of unity."exit                                             /*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 = 1200item = list(limit+1)item[1] = 1item[2] = 1nr = 2gcd = 1gcdall = 1for num = 3 to limit      item[num] = item[nr] + item[nr-1]      item[num+1] = item[nr]      nr = nr + 1       num = num + 1nextshowarray(item,15) for x = 1 to 100      if x < 11 or x = 100         totalitem(x)      oknext for n = 1 to len(item) - 1      if gcd(item[n],item[n+1]) != 1         gcdall = gcd      oknext if gcdall = 1   see "Correct: The first 999 consecutive pairs are relative prime!" + nlok  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!
```

## 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]  endend 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( "," )}" )printlnfor( n <- 1 to 10; pos = sbSeq.indexOf(n) + 1 ) println( s"Position of first \$n is at \$pos" )printlnprintln( s"Position of first 100 is at \${sbSeq.indexOf(100) + 1}" )printlnprintln( 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
```

## Sidef

Translation of: Perl
`# Declare a function to generate the Stern-Brocot sequencefunc 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
```

## 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/2891proc 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 'consideredj = 2 'precedentn = 0 'loop counterDo	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 + 1Loop 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	NextEnd Function Function ShowFirstInstance(n)	For i = 0 To UBound(sb)		If sb(i) = n Then			ShowFirstInstance = i + 1			Exit For		End If	NextEnd 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 SystemImports System.Collections.GenericImports 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 SubEnd 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.
```

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