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>

 

 

 

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

First 100 found at 1179

GCDs of all two consecutive members are one.</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++}}==

#include <iostream>

#include <iomanip>

return 0;

}

{{out}}

<pre>

 

CORRECT: ALL GCDs ARE '1'!

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

All GCDs are 1.

</pre>

 

=={{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]

[(100,1179)]

True</pre>

 

=={{header|JavaScript}}==

'use strict';

 

// MAIN ---

return main();

{{Out}}

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

[100,1179]

true</pre>

 

=={{header|jq}}==

 

'''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}}

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]

Index of 100 first occurrence: 1179

The first 999 consecutive pairs are all coprime.</pre>

 

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

 

 

 

 

# sternBrocot :: Generator [Int]

def sternBrocot():

def go(xs):

 

 

 

 

sbs = take(1200)(sternBrocot())

ixSB = zip(sbs, enumFrom(1))

)

)

 

 

 

 

 

 

 

 

 

 

 

 

 

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

def fst(tpl):

return tpl[0]

 

# head :: [a] -> a

def head(xs):

return xs[0]

 

 

# nubBy :: (a -> a -> Bool) -> [a] -> [a]

def nubBy(p):

def go(xs):

return []

 

 

# on :: (b -> b -> c) -> (a -> b) -> a -> a -> c

def on(f):

return lambda g: lambda a: lambda b: f(g(a))(g(b))

 

 

 

 

# take :: Int -> String -> String

def take(n):

return lambda xs: (

xs[0:n]

 

 

 

 

 

 

{{Out}}

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

[(100, 1179)]

True</pre>

 

=={{header|R}}==

{{trans|PARI/GP}}

{{Works with|R|3.3.2 and above}}

 

## Stern-Brocot sequence

## 12/19/16 aev

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

}

 

{{Output}}

>

</pre>

 

 

;; OEIS Definition

;; A002487

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

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

 

{{out}}

didn't find gcd > (or otherwise ≠) 1</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>