Stern-Brocot sequence: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|Clojure}}: Add implementation.)
Line 103: Line 103:
return b;
return b;
}</lang>
}</lang>
=={{header|Clojure}}==
<lang clojure>;; 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)))))))</lang>

{{Output}}

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


=={{header|D}}==
=={{header|D}}==

Revision as of 04:32, 31 December 2014

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

The task is to
  1. Create a function/method/subroutine/procedure/... to generate the Stern-Brocot sequence of integers using the method outlined above.
  2. 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)
  3. Show the (1-based) index of where the numbers 1-to-10 first appears in the sequence.
  4. Show the (1-based) index of where the number 100 first appears in the sequence.
  5. Check that the greatest common divisor of all the two consecutive members of the series up to the 1000th member, is always one.

Show your output on the page.

Ref
Related Tasks

C

Recursive function. <lang c>#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; }</lang>

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. <lang c>uint f(uint n) { uint a = 1, b = 0; while (n) { if (n&1) b += a; else a += b; n >>= 1; } return b; }</lang>

Clojure

<lang clojure>;; 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)))))))</lang>
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.

D

Translation of: Python

<lang d>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.");

}</lang>

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: <lang d>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;

}</lang>

Output:
7004

Direct Version:

Translation of: C

<lang d>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;

}</lang>

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

Go

<lang 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 task func gcd(x, y int) int { 

   for y != 0 {
       x, y = y, x%y
   }
   return x

}</lang> <lang go>// 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
       }
   }

}</lang>

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

<lang haskell>import Data.List

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

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

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:

<lang J>sternbrocot=:1 :0 

 ind=. 0
 seq=. 1 1
 while. -. u seq do.
   ind=. ind+1
   seq=. seq, +/\. seq {~ _1 0 +ind
 end.

)</lang>

First fifteen members of the sequence:

<lang J> 15{.(15<:#) sternbrocot 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4</lang>

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

<lang J> 1+(10 e. ]) sternbrocot i.1+i.10 1 3 5 9 11 33 19 21 35 39</lang>

One based index of where the number 100 first appears:

<lang J> 1+(100 e. ]) sternbrocot i. 100 1179</lang>

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

<lang J> ~.2 +./\ (1000<:#) sternbrocot 1</lang>

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. <lang java5>import java.math.BigInteger; import java.util.LinkedList;

public class SternBrocot { static LinkedList<Integer> sequence = new LinkedList<Integer>()Template: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"); } }</lang>

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

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: <lang jq>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 ;</lang>

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. <lang jq># If n is non-negative, then A002487(n)

  1. generates an array with at least n elements of
  2. the A002487 sequence;
  3. if n is negative, elements are added until (-n)
  4. 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 ) ;</lang> The tasks: <lang jq># Generate a stream of n integers beginning with 1,1... def stern_brocot(n): A002487(n+1) | .[1:n+1][];

  1. Return the index (counting from 1) of n in the
  2. 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 </lang>

Output:

<lang sh>$ 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</lang>

Perl

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

   }

}</lang>

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

Perl 6

<lang perl6>constant Stern-Brocot = flat 

   1, 1, -> *@a {
       @a[$_ - 1] + @a[$_], @a[$_] given ++$;
   } ... *;

say Stern-Brocot[^15];

for 1 .. 10, 100 -> $ix { 

   say "first occurrence of $ix is at index : ", 1 + Stern-Brocot.first-index($ix);

}

say so 1 == all map ^1000: { [gcd] Stern-Brocot[$_, $_ + 1] }</lang>

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

Python

Python: procedural

<lang python>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'</lang>
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' <lang python>>>> 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 >>> </lang>

Racket

<lang racket>#lang racket

OEIS Definition
A002487
Stern's diatomic series
(or Stern-Brocot sequence)
a(0) = 0, a(1) = 1;
for n > 0
a(2*n) = a(n),
a(2*n+1) = a(n) + a(n+1).

(define A002487 

 (let ((memo (make-hash '((0 . 0) (1 . 1)))))
   (lambda (n)
     (hash-ref! memo n
                (lambda ()
                  (define n/2 (quotient n 2))
                  (+ (A002487 n/2) (if (even? n) 0 (A002487 (add1 n/2)))))))))

(define Stern-Brocot A002487)

(displayln "Show the first fifteen members of the sequence. (This should be: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4)") (for/list ((i (in-range 1 (add1 15)))) (Stern-Brocot i))

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

 (for/first ((i (in-naturals 1))
             #:when (= n (Stern-Brocot i)))
   (printf "~a first found at a(~a)~%" n i)))

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

(displayln "Check that the greatest common divisor of all the two consecutive members of the series up to the 1000th member, is always one.") (unless 

   (for/first ((i (in-range 1 1000))
               #:unless (= 1 (gcd (Stern-Brocot i) (Stern-Brocot (add1 i))))) #t)
 (display "\tdidn't find gcd > (or otherwise ≠) 1"))</lang>
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

This REXX program could've been made simpler by including a GCD function that ignores zeroes and negative numbers, and also only processes two numbers. <lang rexx>/*REXX pgm gens/shows Stern-Brocot sequence, finds 1-based indices, GCDs*/ parse arg N idx fix chk . /*get optional argument from C.L.*/ if N== | N==',' then N= 15 /*use the default for N ? */ 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 seq*/ say a /*display sequence to terminal. */ 

                                      /*═══════════════════════════════*/

say center('the 1-based index for the first' idx "integers", 70, '═') a=Stern_Brocot(-idx) /*invoke function to generate seq*/ 

      do i=1  for idx
      say 'for '  right(i,length(idx))",  the index is: "    wordpos(i,a)
      end   /*i*/
                                      /*═══════════════════════════════*/

say center('the 1-based index for' fix, 70, '═') a=Stern_Brocot(-fix) /*invoke function to generate seq*/ say 'for ' fix", the index is: " wordpos(fix,a) 

                                      /*═══════════════════════════════*/

say center('checking if all two consecutive members have a GCD=1', 70,'═') a=Stern_Brocot(chk) /*invoke function to generate seq*/ 

      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 done.*/ /*──────────────────────────────────GCD subroutine──────────────────────*/ gcd: procedure; $=; do i=1 for arg(); $=$ arg(i); end /*arg list*/ parse var $ x z .; if x=0 then x=z /*handle special 0 case.*/ x=abs(x) 

         do j=2  to words($);  y=abs(word($,j));  if y=0  then iterate
           do  until _==0; _=x//y; x=y; y=_; end     /*◄──heavy lifting*/
         end   /*j*/

return x /*──────────────────────────────────STERN_BROCOT subroutine.────────────*/ Stern_Brocot: parse arg h 1 f; if h<0 then h=1e9; else f=0; f=abs(f) $=1 1 

      do k=2  until  words($)>=h;   _=word($,k);    $=$ (_+word($,k-1)) _
      if f==0  then iterate;        if wordpos(f,$)\==0  then leave
      end   /*until*/

if f==0 then return subword($,1,h) 

             return $</lang>

output when using the default inputs: 

══════════the first 15 numbers in the Sterm-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

<lang ruby>def sb 

 return enum_for :sb unless block_given?
 a=[1,1]
 i=0
 loop do
   yield a[i]
   a += [a[i] + a[i+1], a[i+1]]
   i+=1
 end

end

puts "First 15: #{sb.take(15).join ', '}"

[*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 } then 

 puts "All GCD's are 1"

else 

 puts "Whoops, not all GCD's are 1!"

end</lang>

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

zkl

<lang 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") }</lang>

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)
Retrieved from "https://rosettacode.org/wiki/Stern-Brocot_sequence?oldid=251971"