Stern-Brocot sequence: Difference between revisions

#*     1, 1, 2, 1

# Consider the next member of the series, (the third member i.e. 2)

#*         ─── Expanding another loop we get: ───

#*

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

;Ref:

* [https://www.youtube.com/watch?v=DpwUVExX27E Infinite Fractions - Numberphile] (Video).

* [https://oeis.org/A002487 A002487] The On-Line Encyclopedia of Integer Sequences.

<br><br>

 

=={{header|360 Assembly}}==

{{trans|Fortran}}

STERNBR CSECT

USING STERNBR,R13 base register

SB DC (NN)H'1' sb(nn)

REGEQU

{{out}}

<pre>

</pre>

The nice part is the coding of the sequense:

while(k<nn);

k++; sb[k]=sb[k-i]+sb[k-j];

k++; sb[k]=sb[k-j];

i++; j++;

Only five registers are used. No Horner's rule to access sequence items.

LA R2,SB+2 i=1; @sb(k-i)

LA R3,SB+0 j=2; @sb(k-j)

STH R0,0(R4) sb(k)=sb(k-j)

LA R2,2(R2) @sb(k-i)++

 

=={{header|8080 Assembly}}==

org 100h

;;; Generate the first 1200 elements of the Stern-Brocot sequence

gcdn: db 'GCD not 1 at: $'

gcdy: db 'GCD of all pairs of consecutive members is 1.$'

 

{{out}}

 

=={{header|8086 Assembly}}==

cpu 8086

bits 16

numbuf: db ' $'

nl: db 13,10,'$'

 

{{out}}

GCD of all pairs of consecutive members is 1.</pre>

 

 

 

 

 

procedure Sequence is

when Constraint_Error => Put_Line("Some GCD > 1; this is wrong!!!") ;

end;

 

{{out}}

First 9 at 35; First 10 at 39; First 100 at 1179.

Correct: The first 999 consecutive pairs are relative prime!</pre>

 

=={{header|AppleScript}}==

use framework "Foundation"

use scripting additions

 

 

-- sternBrocot :: Generator [Int]

 

 

on run

set sbs to take(1200, sternBrocot())

 

 

 

-- Absolute value.

end if

end abs

 

-- Applied to a predicate and a list, `all` determines if all elements

end tell

end all

 

-- comparing :: (a -> b) -> (a -> a -> Ordering)

end if

end drop

 

-- dropWhile :: (a -> Bool) -> [a] -> [a]

drop(i - 1, xs)

end dropWhile

 

-- enumFrom :: a -> [a]

end script

end enumFrom

 

-- filter :: (a -> Bool) -> [a] -> [a]

end tell

end filter

 

-- fmapGen <$> :: (a -> b) -> Gen [a] -> Gen [b]

end script

end fmapGen

 

-- fst :: (a, b) -> a

end if

end fst

 

-- gcd :: Int -> Int -> Int

return x

end gcd

 

-- head :: [a] -> a

end if

end head

 

-- iterate :: (a -> a) -> a -> Gen [a]

end if

end min

 

-- Lift 2nd class handler function into 1st class script wrapper

go's |λ|(xs)

end nubBy

 

-- partition :: predicate -> List -> (Matches, nonMatches)

Tuple(ys, zs)

end partition

 

-- showJSON :: a -> String

end if

end showJSON

 

-- snd :: (a, b) -> b

end if

end sortBy

 

-- tail :: [a] -> [a]

end if

end tail

 

-- take :: Int -> [a] -> [a]

end if

end take

 

-- takeWhile :: (a -> Bool) -> [a] -> [a]

end if

end takeWhile

 

-- takeWhileGen :: (a -> Bool) -> Gen [a] -> [a]

return ys

end takeWhileGen

 

-- Tuple (,) :: a -> b -> (a, b)

{type:"Tuple", |1|:a, |2|:b, length:2}

end Tuple

 

-- unlines :: [String] -> String

str

end unlines

 

-- zip :: [a] -> [b] -> [(a, b)]

zipWith(Tuple, xs, ys)

end zip

 

-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

return lst

end tell

{{Out}}

<pre>[1,1,2,1,3,2,3,1,4,3,5,2,5,3,4]

[100,1179]

true</pre>

 

=={{header|AutoHotkey}}==

Loop, 10

FoundList .= "First " A_Index " found at " Found[A_Index] "`n"

b := Mod(a | 0x0, a := b)

return a

{{out}}

<pre>First 15: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4

 

=={{header|BASIC}}==

20 S(1)=1: S(2)=1

30 FOR I=2 TO 600

190 NEXT I

200 PRINT "All GCDs are 1."

 

{{out}}

All GCDs are 1.

</pre>

 

=={{header|C}}==

Recursive function.

 

typedef unsigned int uint;

 

return 0;

{{out}}

<pre>

</pre>

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

{

uint a = 1, b = 0;

}

return b;

 

=={{header|C sharp|C#}}==

using System.Collections.Generic;

using System.Linq;

" series up to the {0}th item is {1}always one.", max, good ? "" : "not ");

}

{{out}}

<pre>The first 15 items In the Stern-Brocot sequence: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4

 

=={{header|C++}}==

#include <iostream>

#include <iomanip>

return 0;

}

{{out}}

<pre>

 

=={{header|Clojure}}==

(defn sb-step [v]

(let [i (quot (count v) 2)]

true)

 

 

{{Output}}

 

===Clojure: Using Lazy Sequences===

(defn gcd

"(gcd a b) computes the greatest common divisor of a and b."

(println (every? (fn [[ith ith-plus-1]] (= (gcd ith ith-plus-1) 1))

one-thousand-pairs))

{{Output}}

 

true

</pre>

 

=={{header|Common Lisp}}==

(declare ((or null (vector integer)) numbers))

(cond ((null numbers)

(first-1-to-10)

(first-100)

{{out}}

<pre>First 15: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4

First 100 at 1179

Correct. The GCDs of all the two consecutive numbers are 1.</pre>

 

=={{header|D}}==

{{trans|Python}}

 

/// Generates members of the stern-brocot series, in order,

assert(zip(s, s.dropOne).all!(ss => ss[].gcd == 1),

"A fraction from adjacent terms is reducible.");

{{out}}

<pre>The first 15 values:

 

This uses a queue from the Queue/usage Task:

 

struct SternBrocot {

void main() {

SternBrocot().drop(50_000_000).front.writeln;

{{out}}

<pre>7004</pre>

<b>Direct Version:</b>

{{trans|C}}

import std.stdio, std.numeric, std.range, std.algorithm, std.bigint, std.conv;

 

 

sternBrocot(10.BigInt ^^ 20_000).text.length.writeln;

{{out}}

<pre>The first 15 values:

1-based index of the first occurrence of 100 in the series: 1179

7984</pre>

 

=={{header|EchoLisp}}==

=== Function ===

;; stern (2n ) = stern (n)

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

(else (let ((m (/ (1- n) 2))) (+ (stern m) (stern (1+ m)))))))

(remember 'stern)

{{out}}

; generate the sequence and check GCD

(for ((n 10000))

(stern 900000) → 446

(stern 900001) → 2479

 

=== Stream ===

From [https://oeis.org/A002487 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

 

=={{header|Elixir}}==

def sequence do

Stream.unfold({0,{1,1}}, fn {i,acc} ->

end

 

 

{{out}}

=={{header|F_Sharp|F#}}==

===The function===

// Generate Stern-Brocot Sequence. Nigel Galloway: October 11th., 2018

let sb=Seq.unfold(fun (n::g::t)->Some(n,[g]@t@[n+g;g]))[1;1]

===The Task===

Uses [[Greatest_common_divisor#F.23]]

sb |> Seq.take 15 |> Seq.iter(printf "%d ");printfn ""

[1..10] |> List.map(fun n->(n,(sb|>Seq.findIndex(fun g->g=n))+1)) |> List.iter(printf "%A ");printfn ""

printfn "%d" ((sb|>Seq.findIndex(fun g->g=100))+1)

printfn "There are %d consecutive members, of the first thousand members, with GCD <> 1" (sb |> Seq.take 1000 |>Seq.pairwise |> Seq.filter(fun(n,g)->gcd n g <> 1) |> Seq.length)

{{out}}

<pre>

=={{header|Factor}}==

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

math.ranges prettyprint sequences ;

IN: rosetta-code.stern-brocot

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

 

{{out}}

<pre>

First 10 at Stern #39.

First 100 at Stern #1179.

All GCDs are 1.

</pre>

{{trans|VBScript}}

===Fortran IV===

DIMENSION ISB(2400)

NN=2400

103 FORMAT(1X,'FIRST',I4,' AT ',I4)

5 CONTINUE

{{out}}

<pre>

</pre>

===Fortran 90===

parameter (nn=2400)

dimension isb(nn)

write(*,"(1x,'First',i4,' at ',i4)") jj,i

end do

{{out}}

<pre>

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>The first 15 are: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4

 

=={{header|Go}}==

 

import (

}

return x

//

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

}

}

{{out}}

<pre>

 

=={{header|Haskell}}==

 

sb :: [Int]

sb = 1 : 1 : f (tail sb) sb

where

 

main :: IO ()

print

[ (i, 1 + (\(Just i) -> i) (elemIndex i sb))

{{out}}

<pre>[1,1,2,1,3,2,3,1,4,3,5,2,5,3,4]

Or, expressed in terms of iterate:

 

import Data.Ord (comparing)

 

sternBrocot :: [Int]

 

main :: IO ()

main = do

print $

take 10 $

{{Out}}

<pre>[1,1,2,1,3,2,3,1,4,3,5,2,5,3,4]

 

=={{header|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:

 

ind=. 0

seq=. 1 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: <code>u sternbrocot</code>. 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:

 

 

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

 

 

One based index of where the number 100 first appears:

 

 

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

 

 

=={{header|Java}}==

{{works with|Java|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 <code>gcd</code> method from <code>BigInteger</code> rather than using its own.

import java.util.LinkedList;

 

System.out.println("All GCDs are" + (failure ? " not" : "") + " 1");

}

{{out}}

<pre>The first 15 elements are: [1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]

=== Stern-Brocot Tree ===

{{works with|Java|8}}

import javax.swing.*;

 

});

}

[[File:stern_brocot_tree_java.gif]]

 

=={{header|JavaScript}}==

'use strict';

 

// MAIN ---

return main();

{{Out}}

<pre>[1,1,2,1,3,2,3,1,4,3,5,2,5,3,4]

 

'''Foundations:'''

def _until:

if cond then . else (update | _until) end;

else [.[1], .[0] % .[1]] | rgcd

end;

'''The A002487 integer sequence:'''

 

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.

# generates an array with at least n elements of

# the A002487 sequence;

| if (.[$l-2] == -n) then .

else .[$l + 1] = .[$n] + .[$n+1]

'''The tasks:'''

def stern_brocot(n): A002487(n+1) | .[1:n+1][];

 

"",

gcd_task

{{out}}

First 15 integers of the Stern-Brocot sequence

as defined in the task description are:

index of 100 is 1179

 

 

=={{header|Julia}}==

{{trans|Python}}

 

function sternbrocot(f::Function=(x) -> length(x) ≥ 20)::Vector{Int}

rst = Int[1, 1]

while !f(rst)

i += 1

end

else

println("Rejected.")

 

{{out}}

 

Index of first occurrence of 1 in the series: 1

Index of first occurrence of 3 in the series: 5

Index of first occurrence of 4 in the series: 9

 

Assertion: the greatest common divisor of all the two

 

=={{header|Kotlin}}==

 

val sbs = mutableListOf(1, 1)

}

println("all one")

 

{{out}}

 

=={{header|Lua}}==

function sternBrocot (n)

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

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

print("\nTask 4: " .. findFirst(sb, 100))

{{out}}

<pre>Task 2: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4

Task 5: PASS</pre>

 

 

| l i |

ListBuffer new dup add(1) dup add(1) dup ->l

n 2 mod ifFalse: [ dup removeLast drop ] dup freeze ;

 

 

{{out}}

{{Works with|PARI/GP|2.7.4 and above}}

 

\\ Stern-Brocot sequence

\\ 5/27/16 aev

if(j==1, print("Yes"), print("No"));

}

{{Output}}

=={{header|Pascal}}==

{{works with|Free Pascal}}

{$IFDEF FPC}

{$MODE DELPHI}

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

setlength(seq,0);

1 @ 1,2 @ 3,3 @ 5,4 @ 9,5 @ 11,6 @ 33,7 @ 38,8 @ 42,9 @ 47,10 @ 57

100 @ 1179

 

=={{header|Perl}}==

use warnings;

 

($a, $b) = ($b, $generator->());

}

{{out}}

<pre>1 1 2 1 3 2 3 1 4 3 5 2 5 3 4

 

A slightly different method:{{libheader|ntheory}}

 

sub stern_diatomic {

print "The first 999 consecutive pairs are ",

(vecsum( map { gcd(stern_diatomic($_),stern_diatomic($_+1)) } 1..999 ) == 999)

{{out}}

<pre>First fifteen: [1 1 2 1 3 2 3 1 4 3 5 2 5 3 4]

 

=={{header|Phix}}==

{{Out}}

<pre>

{{trans|C}}

Using the <tt>gcd</tt> function defined at ''[[Greatest_common_divisor#PicoLisp]]'':

(let (A 1 B 0)

(while (gt0 N)

(for (L Lst (cdr L) (cddr L))

(test 1 (gcd (car L) (cadr L))) )

{{out}}

<pre>

All consecutive pairs are relative prime!

</pre>

 

=={{header|PowerShell}}==

# An iterative approach

function iter_sb($count = 2000)

'GCD = 1 for first 1000 members: {0}' -f $gcd

}

 

{{out}}

GCD = 1 for first 1000 members: True

</pre>

 

=={{header|Python}}==

===Python: procedural===

"""\

Generates members of the stern-brocot series, in order, returning them when the predicate becomes false

s = stern_brocot(lambda series: len(series) < n_gcd)[:n_gcd]

assert all(gcd(prev, this) == 1

 

{{out}}

 

See the [[Talk:Stern-Brocot_sequence#deque_over_list.3F|talk page]] for how a deque was selected over the use of a straightforward list'

>>> from collections import deque

>>> from fractions import gcd

>>> all(gcd(p, t) == 1 for p, t in islice(zip(prev, this), 1000))

True

 

===Python: Composing pure (curried) functions===

Composing and testing a Stern-Brocot function by composition of generic and reusable functional abstractions (curried for more flexible nesting and rearrangement).

{{Works with|Python|3.7}}

 

import operator

 

 

def sternBrocot():

'''Non-finite list of the Stern-Brocot

def go(xs):

 

 

# main :: IO ()

def main():

 

 

 

# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c

'''True if p(x) holds for every x in xs'''

return lambda xs: all(map(p, xs))

 

 

'''The first element of a non-empty list.'''

return xs[0]

 

 

'''A sublist of xs from which all duplicates,

(as defined by the equality predicate p)

def go(xs):

if not xs:

))

)

 

 

return xs[1:]

else:

return xs

 

else list(islice(xs, n))

)

 

 

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>[1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4]

[(100, 1179)]

True</pre>

 

=={{header|R}}==

{{libheader|pracma}}

 

## Stern-Brocot sequence

## 12/19/16 aev

if(j==1) {cat(" *** All GCDs=1!\n")} else {cat(" *** All GCDs!=1??\n")}

}

 

{{Output}}

 

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

{

{

#To show off R's vectorization, the following line is deliberately terse.

#Note that we do not have to initialize a big sternNums array to do this.

#True to the algorithm, the new entries are appended to the end of the old sequence.

}

}

#N=5000 was picked arbitrarily. The code runs very fast regardless of this number being much more than we need.

match(1:10, firstFiveThousandTerms)

match(100, firstFiveThousandTerms)

{{Output}}

> match(1:10, firstFiveThousandTerms)

[1] 1 3 5 9 11 33 19 21 35 39

> match(100, firstFiveThousandTerms)

[1] 1179

[1] TRUE</pre>

 

=={{header|Racket}}==

;; OEIS Definition

;; A002487

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

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

 

{{out}}

(formerly Perl 6)

{{works with|rakudo|2017-03}}

 

 

}

 

{{out}}

<pre>1 1 2 1 3 2 3 1 4 3 5 2 5 3 4

True</pre>

 

=={{header|REXX}}==

parse arg N idx fix chk . /*get optional arguments from the C.L. */

 

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

say

end /*i*/

say

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

say

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

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

say 'GCD check failed at index' c; exit 13

end /*c*/

say '───── All ' chk " two consecutive members have a GCD of unity."

/*──────────────────────────────────────────────────────────────────────────────────────*/

end /*i*/

x=abs(x) /*use absolute x*/

do j=2 to words($); y=abs( word($, j) )

return x /*return the GCD*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

end /*k*/

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

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

=={{header|Ring}}==

# Project : Stern-Brocot sequence

 

end

return gcd

Output:

<pre>

Correct: The first 999 consecutive pairs are relative prime!

</pre>

 

=={{header|Ruby}}==

{{works with|Ruby|2.1}}

return enum_for :sb unless block_given?

a=[1,1]

else

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

 

{{out}}

 

=={{header|Scala}}==

BigInt("1") #::

BigInt("1") #::

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

}

 

{{out}}

</pre>

 

=={{header|Sidef}}==

{{trans|Perl}}

func stern_brocot {

var list = [1, 1]

} * 1000

 

{{out}}

<pre>

</pre>

 

 

private var seq = [1, 1]

 

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

 

 

{{out}}

 

=={{header|Tcl}}==

#!/usr/bin/env tclsh

#

 

main

{{Out}}

<pre>

 

=={{header|VBScript}}==

i = 1 'considered

j = 2 'precedent

End If

Next

{{Out}}

<pre>First 15: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4

=={{header|Visual Basic .NET}}==

{{trans|C#}}

Imports System.Collections.Generic

Imports System.Linq

" series up to the {0}th item is {1}always one.", max, If(good, "", "not "))

End Sub

{{out}}

<pre>The first 15 items In the Stern-Brocot sequence: 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4

 

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

</pre>

 

=={{header|zkl}}==

{ Walker(fcn(sb,n){ a,b:=sb; sb.append(a+b,b); sb.del(0); a }.fp(L(1,1))) }

 

[1..].zip(SB()).filter1(fcn(sb){ 100==sb[1] }).println();

 

{{out}}

<pre>