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

Show your output on this page.



Related tasks

   Fusc sequence.
   Continued fraction/Arithmetic


Ref

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


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