Stern-Brocot sequence: Difference between revisions

{{trans|Python}}

 

V sb = [1, 1]

V i = 0

V n_gcd = 1000

V s = stern_brocot(series -> series.len < :n_gcd)[0 .< n_gcd]

 

{{out}}

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

 

=={{header|Action!}}==

INT i

 

PrintLoc(seq,count,loc,11)

PrintGcd(seq,1000)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Stern-Brocot_sequence.png Screenshot from Atari 8-bit computer]

=={{header|Ada}}==

 

 

procedure Sequence is

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

end;

 

{{out}}

 

=={{header|ALGOL 68}}==

# subsequent members are the previous two members summed followed by #

# the previous #

OD;

print( ( "Element pairs up to 1000 are ", IF all coprime THEN "" ELSE "NOT " FI, "coprime", newline ) )

{{out}}

<pre>

 

=={{header|ALGOL-M}}==

integer array S[1:1200];

integer i,ok;

end;

if ok = 1 then write("The GCD of each pair of consecutive members is 1.");

{{out}}

<pre>First 15 numbers:

=={{header|Amazing Hopper}}==

Version: hopper-FLOW!:

#include <flow.h>

#include <flow-flow.h>

NEXT

RET

{{out}}

<pre>

=={{header|APL}}==

 

stern←{⍵{

⍺←0 ⋄ ⍺⍺≤⍴⍵:⍺⍺↑⍵

⎕←'Location of 100:',seq⍳100

⎕←'All GCDs 1:','no' 'yes'[1+1∧.=2∨/1000↑seq]

 

{{out}}

 

=={{header|AppleScript}}==

use framework "Foundation"

use scripting additions

return lst

end tell

{{Out}}

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

 

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

==={{header|BASIC256}}===

{{trans|FreeBASIC}}

max = 2000

global stern

else

print "The GCD for index "; i; " and "; i+1; " = "; d

{{out}}

<pre>Igual que la entrada de FreeBASIC.</pre>

{{trans|FreeBASIC}}

{{works with|QBasic|1.1}}

DIM SHARED stern(max + 2)

 

ELSE

PRINT "The GCD for index "; i; " and "; i + 1; " = "; d

{{out}}

<pre>Igual que la entrada de FreeBASIC.</pre>

==={{header|Yabasic}}===

{{trans|FreeBASIC}}

dim stern(limite+2)

 

else

print "The GCD for index ", i, " and ", i+1, " = ", d

{{out}}

<pre>Igual que la entrada de FreeBASIC.</pre>

 

=={{header|BCPL}}==

 

manifest $( AMOUNT = 1200 $)

$) then

writes("*NThe GCD of each pair of consecutive members is 1.*N")

{{out}}

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

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

 

 

=={{header|CLU}}==

s: array[int] := array[int]$fill(1, n, 1)

for i: int in int$from_to(2, n/2) do

stream$putl(po, "The GCD of the pair at " || int$unparse(i) || " is not 1.")

end

{{out}}

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

 

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

 

=={{header|Cowgol}}==

 

# Redefining these is enough to change the type and length everywhere,

end loop;

 

 

{{out}}

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

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

=={{header|Forth}}==

 

dup 2 >= if

2 /mod swap if

 

task

 

{{out}}

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

print $

all (\(a, b) -> 1 == gcd a b) $

{{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.List (nubBy, sortOn)

import Data.Ord (comparing)

print $

(all ((1 ==) . uncurry gcd) . (zip <*> tail)) $

{{Out}}

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

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}

else

println("Rejected.")

 

{{out}}

 

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

=={{header|MAD}}==

 

VECTOR VALUES FRST15 = $20HFIRST 15 NUMBERS ARE*$

VECTOR VALUES FRSTAT = $6HFIRST ,I3,S1,11HAPPEARS AT ,I4*$

SCAN WHENEVER N .E. STERN(K), FUNCTION RETURN K

END OF FUNCTION

 

{{out}}

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Do[

sb = sb~Join~{Total@sb[[i - 1 ;; i]], sb[[i]]}

Flatten[FirstPosition[sb, #] & /@ Range[10]]

First@FirstPosition[sb, 100]

{{out}}

<pre>{1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4}

 

=={{header|Modula-2}}==

FROM InOut IMPORT WriteString, WriteCard, WriteLn;

 

WriteString("The GCD of every pair of adjacent elements is 1.");

WriteLn;

{{out}}

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

We use an iterator and store the values in a sequence. To reduce memory usage, we could replace the sequence with a deque and pop the previous value at each round. But it’s no worth to complete the task.

 

 

iterator sternBrocot(): (int, int) =

echo "Found two successive terms at index: ", index

else:

 

{{out}}

=={{header|Oforth}}==

 

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

<span style="color: #004080;">sequence</span> <span style="color: #000000;">sb</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>

<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"max gcd:%d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">maxgcd</span><span style="color: #0000FF;">})</span>

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

 

=={{header|PL/I}}==

%replace MAX by 1200;

declare S(1:MAX) fixed;

end;

put skip list('All GCDs of adjacent pairs are 1.');

{{out}}

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

 

=={{header|PL/M}}==

/* FIND LOCATION OF FIRST ELEMENT IN ARRAY */

FIND$FIRST: PROCEDURE (ARR, EL) ADDRESS;

CALL PRINT(.'ALL GCDS ARE 1$');

CALL BDOS(0,0);

{{out}}

<pre>FIRST 15 ELEMENTS: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4

 

=={{header|PowerShell}}==

# An iterative approach

function iter_sb($count = 2000)

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

}

 

{{out}}

 

=={{header|PureBasic}}==

Define.i i

 

EndIf

 

{{out}}

<pre>Stern-Brocot_sequence

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

# MAIN ---

if __name__ == '__main__':

{{Out}}

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

=={{header|Quackery}}==

 

tuck mod again ]

drop abs ] is gcd ( n n --> n )

[ say "Reducible pair found." ]

else

 

{{out}}

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

{

sternNums <- c(1, 1)

match(1:10, firstFiveThousandTerms)

match(100, firstFiveThousandTerms)

{{Output}}

<pre>> firstFiveThousandTerms <- genNStern(5000)

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

 

put @Stern-Brocot[^15];

}

 

{{out}}

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

 

=={{header|REXX}}==

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

if N=='' | N=="," then N= 15 /*Not specified? Then use the default.*/

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>

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

{{works with|Chez Scheme}}

'''The Function'''

 

(define stern-brocot

(else

(let ((earlier (/ (1+ n) 2)))

'''The Task'''

 

(printf "First 15 Stern-Brocot numbers:")

(set! any-bad #t))))

(when (not any-bad)

{{out}}

<pre>First 15 Stern-Brocot numbers: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4

=={{header|Sidef}}==

{{trans|Perl}}

func stern_brocot {

var list = [1, 1]

} * 1000

 

{{out}}

<pre>

=={{header|Snobol}}==

 

DEFINE('GCD(A,B)') :(GCD_END)

GCD GCD = A

GCDFAIL OUTPUT = "GCD is not 1 at " IX "."

 

 

{{out}}

=={{header|Swift}}==

 

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

{{libheader|Wren-math}}

{{libheader|Wren-fmt}}

import "/fmt" for Fmt

 

p = p + 2

}

 

{{out}}

 

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