Stern-Brocot sequence: Difference between revisions
→OCaml: add
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(→OCaml: add) |
||
Line 11:
#* 1, 1, 2, 1
# Consider the next member of the series, (the third member i.e. 2)
# GOTO 3
#*
#* ─── Expanding another loop we get: ───
#*
Line 25:
* 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
* 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.
Line 39:
;Ref:
* [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].
* [https://oeis.org/A002487 A002487] The On-Line Encyclopedia of Integer Sequences.
<br><br>
Line 199:
=={{header|8080 Assembly}}==
<syntaxhighlight lang="8080asm">puts: equ 9 ; CP/M syscall to print a string
org 100h
Line 345 ⟶ 344:
=={{header|8086 Assembly}}==
<syntaxhighlight lang="asm">puts: equ 9
cpu 8086
Line 454 ⟶ 452:
1179
GCD of all pairs of consecutive members is 1.</pre>
=={{header|Action!}}==
Line 556 ⟶ 552:
=={{header|Ada}}==
<syntaxhighlight lang="ada">with Ada.Text_IO, Ada.Containers.Vectors;
Line 876 ⟶ 871:
=={{header|APL}}==
<syntaxhighlight lang="apl">task←{
stern←{⍵{
Line 1,538 ⟶ 1,532:
=={{header|BASIC}}==
<syntaxhighlight lang="basic">10 DEFINT A,B,I,J,S: DIM S(1200)
20 S(1)=1: S(2)=1
Line 1,837 ⟶ 1,830:
The GCD of each pair of consecutive members is 1.</pre>
=={{header|C}}==
Recursive function.
Line 2,667 ⟶ 2,661:
=={{header|Forth}}==
<syntaxhighlight lang="forth">: stern ( n -- x : return N'th item of Stern-Brocot sequence)
dup 2 >= if
Line 3,154 ⟶ 3,147:
=={{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:
Line 3,955 ⟶ 3,947:
=={{header|MAD}}==
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER
VECTOR VALUES FRST15 = $20HFIRST 15 NUMBERS ARE*$
Line 4,205 ⟶ 4,196:
All consecutive terms up to the 1000th member have a GCD equal to one.</pre>
=={{header|
<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)
| l i |
Line 5,115 ⟶ 5,149:
=={{header|Quackery}}==
<syntaxhighlight lang="quackery"> [ [ dup while
tuck mod again ]
Line 5,230 ⟶ 5,263:
=={{header|Racket}}==
<syntaxhighlight lang="racket">#lang racket
;; OEIS Definition
Line 5,545 ⟶ 5,577:
Greatest Common Divisor for first 1000 members is 1: true
</pre>
=={{header|Scheme}}==
{{works with|Chez Scheme}}
Line 5,671 ⟶ 5,704:
=={{header|Snobol}}==
<syntaxhighlight lang="snobol">* GCD function
DEFINE('GCD(A,B)') :(GCD_END)
Line 5,733 ⟶ 5,765:
First 100 at 1179
All GCDs are 1.</pre>
=={{header|Swift}}==
<syntaxhighlight lang="swift">struct SternBrocot: Sequence, IteratorProtocol {
private var seq = [1, 1]
| |||