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

- The first and second members of the sequence are both 1:
- 1, 1

- Start by considering the second member of the sequence
- 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

- Append the considered member of the sequence to the end of the sequence:
- 1, 1, 2, 1

- Consider the next member of the series, (the third member i.e. 2)
- GOTO 3
- ─── Expanding another loop we get: ───

- 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

- Append the considered member of the sequence to the end of the sequence:
- 1, 1, 2, 1, 3, 2

- Consider the next member of the series, (the fourth member i.e. 1)

- The task is to

- 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 1000
^{th}member, is always one.

Show your output on this page.

- Ref

- Infinite Fractions - Numberphile (Video).
- Trees, Teeth, and Time: The mathematics of clock making.
- A002487 The On-Line Encyclopedia of Integer Sequences.

- Related Tasks

## Contents

## Ada[edit]

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!

## AutoHotkey[edit]

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[edit]

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++[edit]

#include <iostream>

#include <iomanip>

#include <algorithm>

#include <vector>

unsigned gcd( unsigned i, unsigned j ) {

return i ? i < j ? gcd( j % i, i ) : gcd( i % j, j ) : j;

}

void createSequence( std::vector<unsigned>& seq, int c ) {

if( 1500 == seq.size() ) return;

unsigned t = seq.at( c ) + seq.at( c + 1 );

seq.push_back( t );

seq.push_back( seq.at( c + 1 ) );

createSequence( seq, c + 1 );

}

int main( int argc, char* argv[] ) {

std::vector<unsigned> seq( 2, 1 );

createSequence( seq, 0 );

std::cout << "First fifteen members of the sequence:\n ";

for( unsigned x = 0; x < 15; x++ ) {

std::cout << seq[x] << " ";

}

std::cout << "\n\n";

for( unsigned x = 1; x < 11; x++ ) {

std::vector<unsigned>::iterator i = std::find( seq.begin(), seq.end(), x );

if( i != seq.end() ) {

std::cout << std::setw( 3 ) << x << " is at pos. #" << 1 + distance( seq.begin(), i ) << "\n";

}

}

std::cout << "\n";

std::vector<unsigned>::iterator i = std::find( seq.begin(), seq.end(), 100 );

if( i != seq.end() ) {

std::cout << 100 << " is at pos. #" << 1 + distance( seq.begin(), i ) << "\n";

}

std::cout << "\n";

unsigned g;

bool f = false;

for( int x = 0, y = 1; x < 1000; x++, y++ ) {

g = gcd( seq[x], seq[y] );

if( g != 1 ) f = true;

std::cout << std::setw( 4 ) << x + 1 << ": GCD (" << seq[x] << ", "

<< seq[y] << ") = " << g << ( g != 1 ? " <-- ERROR\n" : "\n" );

}

std::cout << "\n" << ( f ? "THERE WERE ERRORS --- NOT ALL GCDs ARE '1'!" : "CORRECT: ALL GCDs ARE '1'!" ) << "\n\n";

return 0;

}

- Output:

First fifteen members of the sequence: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 is at pos. #1 2 is at pos. #3 3 is at pos. #5 4 is at pos. #9 5 is at pos. #11 6 is at pos. #33 7 is at pos. #19 8 is at pos. #21 9 is at pos. #35 10 is at pos. #39 100 is at pos. #1179 1: GCD (1, 1) = 1 2: GCD (1, 2) = 1 3: GCD (2, 1) = 1 4: GCD (1, 3) = 1 5: GCD (3, 2) = 1 6: GCD (2, 3) = 1 7: GCD (3, 1) = 1 8: GCD (1, 4) = 1 [...] 993: GCD (26, 21) = 1 994: GCD (21, 37) = 1 995: GCD (37, 16) = 1 996: GCD (16, 43) = 1 997: GCD (43, 27) = 1 998: GCD (27, 38) = 1 999: GCD (38, 11) = 1 1000: GCD (11, 39) = 1 CORRECT: ALL GCDs ARE '1'!

## Clojure[edit]

;; compute the Nth (1-based) Stern-Brocot number directly

(defn nth-stern-brocot [n]

(if (< n 2)

n

(let [h (quot n 2) h1 (inc h) hth (nth-stern-brocot h)]

(if (zero? (mod n 2)) hth (+ hth (nth-stern-brocot h1))))))

;; return a lazy version of the entire Stern-Brocot sequence

(defn stern-brocot

([] (stern-brocot 1))

([n] (cons (nth-stern-brocot n) (lazy-seq (stern-brocot (inc n))))))

(printf "Stern-Brocot numbers 1-15: %s%n"

(clojure.string/join ", " (take 15 (stern-brocot))))

(dorun (for [n (concat (range 1 11) [100])]

(printf "The first appearance of %3d is at index %4d.%n"

n (inc (first (keep-indexed #(when (= %2 n) %1) (stern-brocot)))))))

- Output:

Stern-Brocot numbers 1-15: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4 The first appearance of 1 is at index 1. The first appearance of 2 is at index 3. The first appearance of 3 is at index 5. The first appearance of 4 is at index 9. The first appearance of 5 is at index 11. The first appearance of 6 is at index 33. The first appearance of 7 is at index 19. The first appearance of 8 is at index 21. The first appearance of 9 is at index 35. The first appearance of 10 is at index 39. The first appearance of 100 is at index 1179.

### Clojure: Using Lazy Sequences[edit]

(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[edit]

(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[edit]

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:**

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[edit]

### Function[edit]

;; 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[edit]

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[edit]

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

## Go[edit]

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 task

func gcd(x, y int) int {

for y != 0 {

x, y = y, x%y

}

return x

}

// SB implements the Stern-Brocot sequence.

//

// Generator() satisfies RC Task 1. For remaining tasks, Generator could be

// used but FirstN(), and Find() are simpler methods for specific stopping

// criteria. FirstN and Find might also be considered to satisfy Task 1,

// in which case Generator would not really be needed. Anyway, there it is.

package sb

// Seq represents an even number of terms of a Stern-Brocot sequence.

//

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

## Haskell[edit]

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

[ (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

## J[edit]

We have two different kinds of list specifications here (length of the sequence, and the presence of certain values in the sequence). Also the underlying list generation mechanism is somewhat arbitrary. So let's generate the sequence iteratively and provide a truth valued function of the intermediate sequences to determine when we have generated one which is adequately long:

sternbrocot=:1 :0

ind=. 0

seq=. 1 1

while. -. u seq do.

ind=. ind+1

seq=. seq, +/\. seq {~ _1 0 +ind

end.

)

(Grammatical aside: this is an adverb which generates a noun without taking any x/y arguments. So usage is: `u sternbrocot`

. J does have precedence rules, just not very many of them. Users of other languages can get a rough idea of the grammatical terms like this: adverb is approximately like a macro, verb approximately like a function and noun is approximately like a number. Also x and y are J's names for left and right noun arguments, and u and v are J's names for left and right verb arguments. An adverb has a left verb argument. There are some other important constraints but that's probably more than enough detail for this task.)

First fifteen members of the sequence:

15{.(15<:#) sternbrocot

1 1 2 1 3 2 3 1 4 3 5 2 5 3 4

One based indices of where numbers 1-10 first appear in the sequence:

1+(10 e. ]) sternbrocot i.1+i.10

1 3 5 9 11 33 19 21 35 39

One based index of where the number 100 first appears:

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

1179

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

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

1

## Java[edit]

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[edit]

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[edit]

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

**The tasks:**

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

First 15 integers of the Stern-Brocot sequence

as defined in the task description are:

1

1

2

1

3

2

3

1

4

3

5

2

5

3

4

Using an index origin of 1:

index of 1 is 1

index of 2 is 3

index of 3 is 5

index of 4 is 9

index of 5 is 11

index of 6 is 33

index of 7 is 19

index of 8 is 21

index of 9 is 35

index of 10 is 39

index of 100 is 1179

GCDs are all 1

## Julia[edit]

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 rst

end

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

for i in (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100)

occurr = findfirst(x -> x == i, sternbrocot(x -> i ∈ x))

@printf("Index of first occurrence of %3i in the series: %4i\n", i, occurr)

end

print("\nAssertion: the greatest common divisor of all the two\nconsecutive members of the series up to the 1000th member, is always one: ")

sb = sternbrocot(x -> length(x) > 1000)

if all(gcd(prev, this) == 1 for (prev, this) in zip(sb[1:1000], sb[2:1000]))

println("Confirmed.")

else

println("Rejected.")

end

- Output:

First 15 elements of Stern-Brocot series: [1, 1, 2, 1, 3, 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[edit]

// 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[edit]

-- Task 1

function sternBrocot (n)

local sbList, pos, c = {1, 1}, 2

repeat

c = sbList[pos]

table.insert(sbList, c + sbList[pos - 1])

table.insert(sbList, c)

pos = pos + 1

until #sbList >= n

return sbList

end

-- Return index in table 't' of first value matching 'v'

function findFirst (t, v)

for key, value in pairs(t) do

if v then

if value == v then return key end

else

if value ~= 0 then return key end

end

end

return nil

end

-- Return greatest common divisor of 'x' and 'y'

function gcd (x, y)

if y == 0 then

return math.abs(x)

else

return gcd(y, x % y)

end

end

-- Check GCD of adjacent values in 't' up to 1000 is always 1

function task5 (t)

for pos = 1, 1000 do

if gcd(t[pos], t[pos + 1]) ~= 1 then return "FAIL" end

end

return "PASS"

end

-- Main procedure

local sb = sternBrocot(10000)

io.write("Task 2: ")

for n = 1, 15 do io.write(sb[n] .. " ") end

print("\n\nTask 3:")

for i = 1, 10 do print("\t" .. i, findFirst(sb, i)) end

print("\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 Task 3: 1 1 2 3 3 5 4 9 5 11 6 33 7 19 8 21 9 35 10 39 Task 4: 1179 Task 5: PASS

## Oforth[edit]

: 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[edit]

\\ Stern-Brocot sequence

\\ 5/27/16 aev

SternBrocot(n)={

my(L=List([1,1]),k=2); if(n<3,return(L));

for(i=2,n, listput(L,L[i]+L[i-1]); if(k++>=n, break); listput(L,L[i]);if(k++>=n, break));

return(Vec(L));

}

\\ Find the first item in any list starting with sind index (return 0 or index).

\\ 9/11/2015 aev

findinlist(list, item, sind=1)={

my(idx=0, ln=#list); if(ln==0 || sind<1 || sind>ln, return(0));

for(i=sind, ln, if(list[i]==item, idx=i; break;)); return(idx);

}

{

\\ Required tests:

my(v,j);

v=SternBrocot(15);

print1("The first 15: "); print(v);

v=SternBrocot(1200);

print1("The first [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[edit]

program StrnBrCt;

{$IFDEF FPC}

{$MODE DELPHI}

{$ENDIF}

const

MaxCnt = 10835282;{ seq[i] < 65536 = high(Word) }

//MaxCnt = 500*1000*1000;{ 2Gbyte -> real 0.85 s user 0.31 }

type

tSeqdata = word;//cardinal LongWord

pSeqdata = pWord;//pcardinal pLongWord

tseq = array of tSeqdata;

function SternBrocotCreate(size:NativeInt):tseq;

var

pSeq,pIns : pSeqdata;

PosIns : NativeInt;

sum : tSeqdata;

Begin

setlength(result,Size+1);

dec(Size); //== High(result)

pIns := @result[size];// set at end

PosIns := -size+2; // negative index campare to 0

pSeq := @result[0];

sum := 1;

pSeq[0]:= sum;pSeq[1]:= sum;

repeat

pIns[PosIns+1] := sum;//append copy of considered

inc(sum,pSeq[0]);

pIns[PosIns ] := sum;

inc(pSeq);

inc(PosIns,2);sum := pSeq[1];//aka considered

until PosIns>= 0;

setlength(result,length(result)-1);

end;

function FindIndex(const s:tSeq;value:tSeqdata):NativeInt;

Begin

result := 0;

while result <= High(s) do

Begin

if s[result] = value then

EXIT(result+1);

inc(result);

end;

end;

function gcd_iterative(u, v: NativeInt): NativeInt;

//http://rosettacode.org/wiki/Greatest_common_divisor#Pascal_.2F_Delphi_.2F_Free_Pascal

var

t: NativeInt;

begin

while v <> 0 do begin

t := u;u := v;v := t mod v;

end;

gcd_iterative := abs(u);

end;

var

seq : tSeq;

i : nativeInt;

Begin

seq:= SternBrocotCreate(MaxCnt);

// Show the first fifteen members of the sequence.

For i := 0 to 13 do write(seq[i],',');writeln(seq[14]);

//Show the (1-based) index of where the numbers 1-to-10 first appears in the

For i := 1 to 10 do

write(i,' @ ',FindIndex(seq,i),',');

writeln(#8#32);

//Show the (1-based) index of where the number 100 first appears in the sequence.

writeln(100,' @ ',FindIndex(seq,100));

//Check that the greatest common divisor of all the two consecutive members of the series up to the 1000th member, is always one.

i := 999;

if i > High(seq) then

i := High(seq);

Repeat

IF gcd_iterative(seq[i],seq[i+1]) <>1 then

Begin

writeln(' failure at ',i+1,' ',seq[i],' ',seq[i+1]);

BREAK;

end;

dec(i);

until i <0;

IF i< 0 then

writeln('GCD-test is O.K.');

setlength(seq,0);

end.

- Output:

1,1,2,1,3,2,3,1,4,3,5,2,5,3,41 @ 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[edit]

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:

use List::Util qw/first/;

use ntheory qw/gcd vecsum/;

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=$_; first { stern_diatomic($_) == $n } 1..10000 } 1..10;

print "Index of 1-10 first occurrence: [@s]\n";

print "Index of 100 first occurrence: ", (first { 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[edit]

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[edit]

sequence sb = {1,1}

integer c = 2

function stern_brocot(integer n)

while length(sb)<n do

sb &= sb[c]+sb[c-1] & sb[c]

c += 1

end while

return sb[1..n]

end function

sequence s = stern_brocot(15)

puts(1,"first 15:")

?s

integer n = 16, k

sequence idx = tagset(10)

for i=1 to length(idx) do

while 1 do

k = find(idx[i],s)

if k!=0 then exit end if

n *= 2

s = stern_brocot(n)

end while

idx[i] = k

end for

puts(1,"indexes of 1..10:")

?idx

puts(1,"index of 100:")

while 1 do

k = find(100,s)

if k!=0 then exit end if

n *= 2

s = stern_brocot(n)

end while

?k

s = stern_brocot(1000)

integer maxgcd = 1

for i=1 to 999 do

maxgcd = max(gcd(s[i],s[i+1]),maxgcd)

end for

printf(1,"max gcd:%d\n",{maxgcd})

- Output:

first 15:{1,1,2,1,3,2,3,1,4,3,5,2,5,3,4} indexes of 1..10:{1,3,5,9,11,33,19,21,35,39} index of 100:1179 max gcd:1

## PowerShell[edit]

# An iterative approach

function iter_sb($count = 2000)

{

# Taken from RosettaCode GCD challenge

function Get-GCD ($x, $y)

{

if ($y -eq 0) { $x } else { Get-GCD $y ($x%$y) }

}

$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[edit]

### Python: procedural[edit]

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[edit]

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

>>>

## R[edit]

## Stern-Brocot sequence

## 12/19/16 aev

SternBrocot <- function(n){

V <- 1; k <- n/2;

for (i in 1:k)

{ V[2*i] = V[i]; V[2*i+1] = V[i] + V[i+1];}

return(V);

}

## Required tests:

require(pracma);

{

cat(" *** The first 15:",SternBrocot(15),"\n");

cat(" *** The first [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) Loading required package: 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[edit]

#lang racket

;; OEIS Definition

;; A002487

;; Stern's diatomic series

;; (or Stern-Brocot sequence):

;; a(0) = 0, a(1) = 1;

;; for n > 0:

;; a(2*n) = a(n),

;; a(2*n+1) = a(n) + a(n+1).

(define A002487

(let ((memo (make-hash '((0 . 0) (1 . 1)))))

(lambda (n)

(hash-ref! memo n

(lambda ()

(define n/2 (quotient n 2))

(+ (A002487 n/2) (if (even? n) 0 (A002487 (add1 n/2)))))))))

(define Stern-Brocot A002487)

(displayln "Show the first fifteen members of the sequence.

(This should be: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4)")

(for/list ((i (in-range 1 (add1 15)))) (Stern-Brocot i))

(displayln "Show the (1-based) index of where the numbers 1-to-10 first appears in the sequence.")

(for ((n (in-range 1 (add1 10))))

(for/first ((i (in-naturals 1))

#:when (= n (Stern-Brocot i)))

(printf "~a first found at a(~a)~%" n i)))

(displayln "Show the (1-based) index of where the number 100 first appears in the sequence.")

(for/first ((i (in-naturals 1)) #:when (= 100 (Stern-Brocot i))) i)

(displayln "Check that the greatest common divisor of all the two consecutive members of the

series up to the 1000th member, is always one.")

(unless

(for/first ((i (in-range 1 1000))

#:unless (= 1 (gcd (Stern-Brocot i) (Stern-Brocot (add1 i))))) #t)

(display "\tdidn't find gcd > (or otherwise ≠) 1"))

- Output:

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

## REXX[edit]

/*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 /* N not defined? Then use default.*/

if idx=='' | idx=="," then idx= 10 /*IDX " " " " " */

if fix=='' | fix=="," then fix= 100 /*FIX " " " " " */

if chk=='' | chk=="," then chk=1000 /*CHK " " " " " */

say center('the first' N "numbers in the Stern─Brocot sequence", 70, '═')

a=Stern_Brocot(N) /*invoke function to generate sequence.*/

say a /*display the sequence to the terminal.*/

say

say center('the 1-based index for the first' idx "integers", 70, '═')

a=Stern_Brocot(-idx) /*invoke function to generate sequence.*/

do i=1 for idx

say 'for ' right(i,length(idx))", the index is: " wordpos(i,a)

end /*i*/

say

say center('the 1-based index for' fix, 70, "═")

a=Stern_Brocot(-fix) /*invoke function to generate sequence.*/

say 'for ' fix", the index is: " wordpos(fix, a)

say

say center('checking if all two consecutive members have a GCD=1', 70, '═')

a=Stern_Brocot(chk) /*invoke function to generate sequence.*/

do c=1 for chk-1; if gcd(subword(a,c,2))==1 then iterate

say 'GCD check failed at member' 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); end /*i*/ /*arg list. */

parse var $ x z .; if x=0 then x=z; x=abs(x) /*zero case?*/

do j=2 to words($); y=abs(word($,j)); if y=0 then iterate /*ignore 0's*/

do until y==0; parse value x//y y with y x; end /*heavy work*/

end /*j*/

return x /*return 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)) _; if f==0 then iterate

end /*until*/

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.

## Ruby[edit]

def sb

return enum_for :sb unless block_given?

a=[1,1]

0.step do |i|

yield a[i]

a << a[i]+a[i+1] << a[i+1]

end

end

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

[*1..10,100].each do |n|

puts "#{n} first appears at #{sb.find_index(n)+1}."

end

if sb.take(1000).each_cons(2).map { |a,b| a.gcd(b) }.all? { |n| n==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[edit]

lazy val sbSeq: Stream[BigInt] = {

BigInt("1") #::

BigInt("1") #::

(sbSeq zip sbSeq.tail zip sbSeq.tail).

flatMap{ case ((a,b),c) => List(a+b,c) }

}

// Show the results

{

println( s"First 15 members: ${(for( n <- 0 until 15 ) yield sbSeq(n)) mkString( "," )}" )

println

for( n <- 1 to 10; pos = sbSeq.indexOf(n) + 1 ) println( s"Position of first $n is at $pos" )

println

println( s"Position of first 100 is at ${sbSeq.indexOf(100) + 1}" )

println

println( s"Greatest Common Divisor for first 1000 members is 1: " +

(sbSeq zip sbSeq.tail).take(1000).forall{ case (a,b) => a.gcd(b) == 1 } )

}

- Output:

First 15 members: 1,1,2,1,3,2,3,1,4,3,5,2,5,3,4 Position of first 1 is at 1 Position of first 2 is at 3 Position of first 3 is at 5 Position of first 4 is at 9 Position of first 5 is at 11 Position of first 6 is at 33 Position of first 7 is at 19 Position of first 8 is at 21 Position of first 9 is at 35 Position of first 10 is at 39 Position of first 100 is at 1179 Greatest Common Divisor for first 1000 members is 1: true

## Sidef[edit]

# Declare a function to generate the Stern-Brocot sequence

func stern_brocot {

var list = [1, 1]

func {

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

## VBScript[edit]

sb = Array(1,1)

i = 1 'considered

j = 2 'precedent

n = 0 'loop counter

Do

ReDim Preserve sb(UBound(sb) + 1)

sb(UBound(sb)) = sb(UBound(sb) - i) + sb(UBound(sb) - j)

ReDim Preserve sb(UBound(sb) + 1)

sb(UBound(sb)) = sb(UBound(sb) - j)

i = i + 1

j = j + 1

n = n + 1

Loop Until n = 2000

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

For k = 1 To 10

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

Next

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

Function DisplayElements(n)

For i = 0 To n - 1

If i < n - 1 Then

DisplayElements = DisplayElements & sb(i) & ", "

Else

DisplayElements = DisplayElements & sb(i)

End If

Next

End Function

Function ShowFirstInstance(n)

For i = 0 To UBound(sb)

If sb(i) = n Then

ShowFirstInstance = i + 1

Exit For

End If

Next

End Function

- Output:

First 15: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4 The first instance of 1 is in #1. The first instance of 2 is in #3. The first instance of 3 is in #5. The first instance of 4 is in #9. The first instance of 5 is in #11. The first instance of 6 is in #33. The first instance of 7 is in #19. The first instance of 8 is in #21. The first instance of 9 is in #35. The first instance of 10 is in #39. The first instance of 100 is in #1179.

## Tcl[edit]

#!/usr/bin/env tclsh

#

package require generator ;# from tcllib

namespace eval stern-brocot {

proc generate {{count 100}} {

set seq {1 1}

set n 0

while {[llength $seq] < $count} {

lassign [lrange $seq $n $n+1] a b

lappend seq [expr {$a + $b}] $b

incr n

}

return $seq

}

proc genr {} {

yield [info coroutine]

set seq {1 1}

while {1} {

set seq [lassign $seq a]

set b [lindex $seq 0]

set c [expr {$a + $b}]

lappend seq $c $b

yield $a

}

}

proc Step {a b args} {

set c [expr {$a + $b}]

list $a [list $b {*}$args $c $b]

}

generator define gen {} {

set cmd [list 1 1]

while {1} {

lassign [Step {*}$cmd] a cmd

generator yield $a

}

}

namespace export {[a-z]*}

namespace ensemble create

}

interp alias {} sb {} stern-brocot

# a simple adaptation of gcd from http://wiki.tcl.tk/2891

proc coprime {a args} {

set gcd $a

foreach arg $args {

while {$arg != 0} {

set t $arg

set arg [expr {$gcd % $arg}]

set gcd $t

if {$gcd == 1} {return true}

}

}

return false

}

proc main {} {

puts "#1. First 15 members of the Stern-Brocot sequence:"

puts \t[generator to list [generator take 16 [sb gen]]]

puts "#2. First occurrences of 1 through 10:"

set first {}

set got 0

set i 0

generator foreach x [sb gen] {

incr i

if {$x>10} continue

if {[dict exists $first $x]} continue

dict set first $x $i

if {[incr got] >= 10} break

}

foreach {a b} [lsort -integer -stride 2 $first] {

puts "\tFirst $a at $b"

}

puts "#3. First occurrence of 100:"

set i 0

generator foreach x [sb gen] {

incr i

if {$x eq 100} break

}

puts "\tFirst $x at $i"

puts "#4. Check first 1k elements for common divisors:"

set prev [expr {2*3*5*7*11*13*17*19+1}] ;# a handy prime

set i 0

generator foreach x [sb gen] {

if {[incr i] >= 1000} break

if {![coprime $x $prev]} {

error "Element $i, $x is not coprime with $prev!"

}

set prev $x

}

puts "\tFirst $i elements are all pairwise coprime"

}

main

- Output:

#1. First 15 members of the Stern-Brocot sequence: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 #2. First occurrences of 1 through 10: First 1 at 1 First 2 at 3 First 3 at 5 First 4 at 9 First 5 at 11 First 6 at 33 First 7 at 19 First 8 at 21 First 9 at 35 First 10 at 39 #3. First occurrence of 100: First 100 at 1179 #4. Check first 1k elements for common divisors: First 1000 elements are all pairwise coprime

## zkl[edit]

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)