Stern-Brocot sequence: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(→OCaml: add) |
||
Line 11: | Line 11: | ||
#* 1, 1, 2, 1 |
#* 1, 1, 2, 1 |
||
# Consider the next member of the series, (the third member i.e. 2) |
# Consider the next member of the series, (the third member i.e. 2) |
||
# GOTO 3 |
# GOTO 3 |
||
#* |
|||
#* |
|||
#* ─── Expanding another loop we get: ─── |
#* ─── Expanding another loop we get: ─── |
||
#* |
#* |
||
Line 25: | Line 25: | ||
* Create a function/method/subroutine/procedure/... to generate the Stern-Brocot sequence of integers using the method outlined above. |
* 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 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 |
* Show the (1-based) index of where the numbers 1-to-10 first appear in the sequence. |
||
* Show the (1-based) index of where the number 100 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 1000<sup>th</sup> member, is always one. |
* Check that the greatest common divisor of all the two consecutive members of the series up to the 1000<sup>th</sup> member, is always one. |
||
Line 39: | Line 39: | ||
;Ref: |
;Ref: |
||
* [https://www.youtube.com/watch?v=DpwUVExX27E Infinite Fractions - Numberphile] (Video). |
* [https://www.youtube.com/watch?v=DpwUVExX27E Infinite Fractions - Numberphile] (Video). |
||
* [http://www.ams.org/samplings/feature-column/fcarc-stern-brocot Trees, Teeth, and Time: The mathematics of clock making]. |
* [http://www.ams.org/samplings/feature-column/fcarc-stern-brocot Trees, Teeth, and Time: The mathematics of clock making]. |
||
* [https://oeis.org/A002487 A002487] The On-Line Encyclopedia of Integer Sequences. |
* [https://oeis.org/A002487 A002487] The On-Line Encyclopedia of Integer Sequences. |
||
<br><br> |
<br><br> |
||
Line 199: | Line 199: | ||
=={{header|8080 Assembly}}== |
=={{header|8080 Assembly}}== |
||
<syntaxhighlight lang="8080asm">puts: equ 9 ; CP/M syscall to print a string |
<syntaxhighlight lang="8080asm">puts: equ 9 ; CP/M syscall to print a string |
||
org 100h |
org 100h |
||
Line 345: | Line 344: | ||
=={{header|8086 Assembly}}== |
=={{header|8086 Assembly}}== |
||
<syntaxhighlight lang="asm">puts: equ 9 |
<syntaxhighlight lang="asm">puts: equ 9 |
||
cpu 8086 |
cpu 8086 |
||
Line 454: | Line 452: | ||
1179 |
1179 |
||
GCD of all pairs of consecutive members is 1.</pre> |
GCD of all pairs of consecutive members is 1.</pre> |
||
=={{header|Action!}}== |
=={{header|Action!}}== |
||
Line 556: | Line 552: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
<syntaxhighlight lang="ada">with Ada.Text_IO, Ada.Containers.Vectors; |
<syntaxhighlight lang="ada">with Ada.Text_IO, Ada.Containers.Vectors; |
||
Line 876: | Line 871: | ||
=={{header|APL}}== |
=={{header|APL}}== |
||
<syntaxhighlight lang="apl">task←{ |
<syntaxhighlight lang="apl">task←{ |
||
stern←{⍵{ |
stern←{⍵{ |
||
Line 1,538: | Line 1,532: | ||
=={{header|BASIC}}== |
=={{header|BASIC}}== |
||
<syntaxhighlight lang="basic">10 DEFINT A,B,I,J,S: DIM S(1200) |
<syntaxhighlight lang="basic">10 DEFINT A,B,I,J,S: DIM S(1200) |
||
20 S(1)=1: S(2)=1 |
20 S(1)=1: S(2)=1 |
||
Line 1,837: | Line 1,830: | ||
The GCD of each pair of consecutive members is 1.</pre> |
The GCD of each pair of consecutive members is 1.</pre> |
||
=={{header|C}}== |
=={{header|C}}== |
||
Recursive function. |
Recursive function. |
||
Line 2,667: | Line 2,661: | ||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
<syntaxhighlight lang="forth">: stern ( n -- x : return N'th item of Stern-Brocot sequence) |
<syntaxhighlight lang="forth">: stern ( n -- x : return N'th item of Stern-Brocot sequence) |
||
dup 2 >= if |
dup 2 >= if |
||
Line 3,154: | Line 3,147: | ||
=={{header|J}}== |
=={{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: |
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: |
||
Line 3,955: | Line 3,947: | ||
=={{header|MAD}}== |
=={{header|MAD}}== |
||
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER |
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER |
||
VECTOR VALUES FRST15 = $20HFIRST 15 NUMBERS ARE*$ |
VECTOR VALUES FRST15 = $20HFIRST 15 NUMBERS ARE*$ |
||
Line 4,205: | Line 4,196: | ||
All consecutive terms up to the 1000th member have a GCD equal to one.</pre> |
All consecutive terms up to the 1000th member have a GCD equal to one.</pre> |
||
=={{header| |
=={{header|OCaml}}== |
||
<syntaxhighlight lang="ocaml">let seq_stern_brocot = |
|||
let rec next x xs () = |
|||
match xs () with |
|||
| Seq.Nil -> assert false |
|||
| Cons (x', xs') -> Seq.Cons (x' + x, Seq.cons x' (next x' xs')) |
|||
in |
|||
let rec tail () = Seq.Cons (1, next 1 tail) in |
|||
Seq.cons 1 tail</syntaxhighlight> |
|||
;<nowiki>Tests:</nowiki> |
|||
<syntaxhighlight lang="ocaml">let rec gcd a = function |
|||
| 0 -> a |
|||
| b -> gcd b (a mod b) |
|||
let seq_index_of el = |
|||
let rec next i sq = |
|||
match sq () with |
|||
| Seq.Nil -> 0 |
|||
| Cons (e, sq') -> if e = el then i else next (succ i) sq' |
|||
in |
|||
next 1 |
|||
let seq_map_pairwise f sq = |
|||
match sq () with |
|||
| Seq.Nil -> Seq.empty |
|||
| Cons (_, sq') -> Seq.map2 f sq sq' |
|||
let () = |
|||
seq_stern_brocot |> Seq.take 15 |> Seq.iter (Printf.printf " %u") |> print_newline |
|||
and () = |
|||
List.iter |
|||
(fun n -> seq_stern_brocot |> seq_index_of n |> Printf.printf " %u@%u" n) |
|||
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 100] |
|||
|> print_newline |
|||
and () = |
|||
seq_stern_brocot |> Seq.take 1000 |> seq_map_pairwise gcd |> Seq.for_all ((=) 1) |
|||
|> Printf.printf " %B\n"</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Oforth}}== |
|||
<syntaxhighlight lang="oforth">: stern(n) |
<syntaxhighlight lang="oforth">: stern(n) |
||
| l i | |
| l i | |
||
Line 5,115: | Line 5,149: | ||
=={{header|Quackery}}== |
=={{header|Quackery}}== |
||
<syntaxhighlight lang="quackery"> [ [ dup while |
<syntaxhighlight lang="quackery"> [ [ dup while |
||
tuck mod again ] |
tuck mod again ] |
||
Line 5,230: | Line 5,263: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
<syntaxhighlight lang="racket">#lang racket |
<syntaxhighlight lang="racket">#lang racket |
||
;; OEIS Definition |
;; OEIS Definition |
||
Line 5,545: | Line 5,577: | ||
Greatest Common Divisor for first 1000 members is 1: true |
Greatest Common Divisor for first 1000 members is 1: true |
||
</pre> |
</pre> |
||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
{{works with|Chez Scheme}} |
{{works with|Chez Scheme}} |
||
Line 5,671: | Line 5,704: | ||
=={{header|Snobol}}== |
=={{header|Snobol}}== |
||
<syntaxhighlight lang="snobol">* GCD function |
<syntaxhighlight lang="snobol">* GCD function |
||
DEFINE('GCD(A,B)') :(GCD_END) |
DEFINE('GCD(A,B)') :(GCD_END) |
||
Line 5,733: | Line 5,765: | ||
First 100 at 1179 |
First 100 at 1179 |
||
All GCDs are 1.</pre> |
All GCDs are 1.</pre> |
||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
<syntaxhighlight lang="swift">struct SternBrocot: Sequence, IteratorProtocol { |
<syntaxhighlight lang="swift">struct SternBrocot: Sequence, IteratorProtocol { |
||
private var seq = [1, 1] |
private var seq = [1, 1] |