Calkin-Wilf sequence: Difference between revisions

Line 35:

* [[Continued fraction/Arithmetic/Construct from rational number]]

=={{header|11l}}==

<syntaxhighlight lang=11l>T CalkinWilf

<syntaxhighlight lang="11l">T CalkinWilf

n = 1

d = 1

Line 70:

Line 69:

The element 83116/51639 is at position 123456789 in the sequence.

</pre>

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

Uses code from the [[Arithmetic/Rational]] and [[Continued fraction/Arithmetic/Construct from rational number]] tasks.

<syntaxhighlight lang=algol68>BEGIN

<syntaxhighlight lang="algol68">BEGIN

# Show elements 1-20 of the Calkin-Wilf sequence as rational numbers #

# also show the position of a specific element in the seuence #

Line 210:

Line 208:

Position of 83116/51639 in the sequence: 123456789

</pre>

=={{header|AppleScript}}==

<syntaxhighlight lang=applescript>-- Return the first n terms of the sequence. Tree generation. Faster for this purpose.

<syntaxhighlight lang="applescript">-- Return the first n terms of the sequence. Tree generation. Faster for this purpose.

on CalkinWilfSequence(n)

script o

Line 312:

Line 309:

<syntaxhighlight lang=applescript>"First twenty terms of sequence using tree generation:

<syntaxhighlight lang="applescript">"First twenty terms of sequence using tree generation:

1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1, 1/5, 5/4, 4/7, 7/3, 3/8

Ditto using binary run-length encoding:

1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1, 1/5, 5/4, 4/7, 7/3, 3/8

83116/51639 is term number 123456789"</syntaxhighlight>

=={{header|Arturo}}==

<syntaxhighlight lang=rebol>n: new 1

<syntaxhighlight lang="rebol">n: new 1

d: new 1

calkinWilf: function [] .export:[n,d] [

Line 354:

Line 350:

The element 83116/51639 is at position 123456789 in the sequence.</pre>

=={{header|BQN}}==

BQN does not have rational number arithmetic yet, so it is manually implemented.

Line 362:

Line 357:

<code>GCD</code> and <code>_while_</code> are idioms from [https://mlochbaum.github.io/bqncrate/ BQNcrate].

<syntaxhighlight lang=bqn>GCD ← {m 𝕊⍟(0<m←𝕨|𝕩) 𝕨}

<syntaxhighlight lang="bqn">GCD ← {m 𝕊⍟(0<m←𝕨|𝕩) 𝕨}

_while_ ← {𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩}

Sim ← { # Simplify a fraction

Line 387:

Line 382:

fr ≢ 83116‿51639

} ⟨1,1‿1⟩</syntaxhighlight>

<syntaxhighlight lang=bqn>⟨ ⟨ 1 2 ⟩ ⟨ 2 1 ⟩ ⟨ 1 3 ⟩ ⟨ 3 2 ⟩ ⟨ 2 3 ⟩ ⟨ 3 1 ⟩ ⟨ 1 4 ⟩ ⟨ 4 3 ⟩ ⟨ 3 5 ⟩ ⟨ 5 2 ⟩ ⟨ 2 5 ⟩ ⟨ 5 3 ⟩ ⟨ 3 4 ⟩ ⟨ 4 1 ⟩ ⟨ 1 5 ⟩ ⟨ 5 4 ⟩ ⟨ 4 7 ⟩ ⟨ 7 3 ⟩ ⟨ 3 8 ⟩ ⟨ 8 5 ⟩ ⟩

<syntaxhighlight lang="bqn">⟨ ⟨ 1 2 ⟩ ⟨ 2 1 ⟩ ⟨ 1 3 ⟩ ⟨ 3 2 ⟩ ⟨ 2 3 ⟩ ⟨ 3 1 ⟩ ⟨ 1 4 ⟩ ⟨ 4 3 ⟩ ⟨ 3 5 ⟩ ⟨ 5 2 ⟩ ⟨ 2 5 ⟩ ⟨ 5 3 ⟩ ⟨ 3 4 ⟩ ⟨ 4 1 ⟩ ⟨ 1 5 ⟩ ⟨ 5 4 ⟩ ⟨ 4 7 ⟩ ⟨ 7 3 ⟩ ⟨ 3 8 ⟩ ⟨ 8 5 ⟩ ⟩

⟨ 123456789 ⟨ 83116 51639 ⟩ ⟩</syntaxhighlight>

You can try Part 1 [https://mlochbaum.github.io/BQN/try.html#code=R0NEIOKGkCB7bSDwnZWK4o2fKDA8beKGkPCdlah88J2VqSkg8J2VqH0KX3doaWxlXyDihpAge/CdlL3ijZ/wnZS+4oiY8J2UvV/wnZWjX/CdlL7iiJjwnZS94o2f8J2UvvCdlal9ClNpbSDihpAgewogIHjwnZWKMTog8J2VqOKAvzE7CiAgMPCdlYp5OiAw4oC/8J2VqTsKICDijIrwnZWo4oC/8J2VqSDDtyDwnZWoIEdDRCDwnZWpCn0KQWRkIOKGkCB7CiAgMOKAv2Ig8J2ViiDwnZWpOiDwnZWpOwogIPCdlagg8J2ViiAw4oC/eTog8J2VqDsKICBh4oC/YiDwnZWKIHjigL95OgogICgoYcOXeSkreMOXYikgU2ltIGLDl3kKfQpOZXh0IOKGkCB7buKAv2Q6IOKMvSgyw5fijIrDt8K0buKAv2Qp4oC/MSBBZGQgKGQtbinigL9kfQpDYWwg4oaQIHtOZXh04o2f8J2VqSAx4oC/MX0KCuKAolNob3cgQ2FsIDEr4oaVMjA= here.] Second part can and will hang your browser, so it is best to try locally on [[CBQN]].

=={{header|Bracmat}}==

<syntaxhighlight lang=bracmat>( 1:?a

<syntaxhighlight lang="bracmat">( 1:?a

& 0:?i

& whl

Line 449:

Line 443:

3/8

123456789</pre>

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

<syntaxhighlight lang=cpp>#include <iostream>

<syntaxhighlight lang="cpp">#include <iostream>

#include <vector>

#include <boost/rational.hpp>

Line 531:

Line 524:

83116/51639 is the 123456789th term of the sequence.

</pre>

=={{header|EDSAC order code}}==

===Find first n terms===

[For Rosetta Code. EDSAC program, Initial Orders 2.

Prints the first 20 terms of the Calkin-Wilf sequence.

Line 642:

Line 634:

===Find index of a given term===

[For Rosetta Code. EDSAC program, Initial Orders 2.]

[Finds the index of a given rational in the Calkin-Wilf series.]

Line 759:

Line 751:

83116/51639 IS AT 123456789

</pre>

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

===The Function===

// Calkin Wilf Sequence. Nigel Galloway: January 9th., 2021

let cW=Seq.unfold(fun(n)->Some(n,seq{for n,g in n do yield (n,n+g); yield (n+g,g)}))(seq[(1,1)])|>Seq.concat

Line 768:

Line 759:

===The Tasks===

; first 20

cW |> Seq.take 20 |> Seq.iter(fun(n,g)->printf "%d/%d " n g);printfn ""

</syntaxhighlight>

Line 776:

Line 767:

</pre>

; Indexof 83116/51639

printfn "%d" (1+Seq.findIndex(fun n->n=(83116,51639)) cW)

</syntaxhighlight>

Line 785:

Line 776:

=={{header|Factor}}==

<syntaxhighlight lang=factor>USING: formatting io kernel lists lists.lazy math

<syntaxhighlight lang="factor">USING: formatting io kernel lists lists.lazy math

math.continued-fractions math.functions math.parser prettyprint

sequences strings vectors ;

Line 813:

Line 804:

83116/51639 is at index 123456789.

</pre>

=={{header|Forth}}==

<syntaxhighlight lang=forth>\ Calkin-Wilf sequence

<syntaxhighlight lang="forth">\ Calkin-Wilf sequence

: frac. swap . ." / " . ;

Line 876:

Line 865:

3 / 8

83116 / 51639 123456789 ok</pre>

=={{header|FreeBASIC}}==

Uses the code from [[Greatest common divisor#FreeBASIC]] as an include.

<syntaxhighlight lang=freebasic>#include "gcd.bas"

<syntaxhighlight lang="freebasic">#include "gcd.bas"

type rational

Line 1,015:

Line 1,001:

20 3/8

83116/51639 is the 123456789th term.</pre>

=={{header|Fōrmulæ}}==

Line 1,023:

Line 1,008:

In '''[https://formulae.org/?example=Calkin-Wilf_correspondence this]''' page you can see the program(s) related to this task and their results.

=={{header|Go}}==

Go just has arbitrary precision rational numbers which we use here whilst assuming the numbers needed for this task can be represented exactly by the 64 bit built-in types.

<syntaxhighlight lang=go>package main

<syntaxhighlight lang="go">package main

import (

Line 1,145:

Line 1,129:

83116/51639 is the 123,456,789th term of the sequence.

</pre>

=={{header|Haskell}}==

<syntaxhighlight lang=haskell>import Control.Monad (forM_)

<syntaxhighlight lang="haskell">import Control.Monad (forM_)

import Data.Bool (bool)

import Data.List.NonEmpty (NonEmpty, fromList, toList, unfoldr)

Line 1,227:

Line 1,210:

83116 % 51639 is at index 123456789 of the Calkin-Wilf sequence.

</pre>

=={{header|J}}==

<pre>

Line 1,239:

Line 1,221:

</pre>

given definitions

cw_next_term=: [: % +:@<. + -.

Line 1,262:

Line 1,244:

index_cw_term=: #.@|.@(# 1 0 $~ #)@molcf@ccf

</syntaxhighlight>

=={{header|Julia}}==

<syntaxhighlight lang=julia>function calkin_wilf(n)

<syntaxhighlight lang="julia">function calkin_wilf(n)

cw = zeros(Rational, n + 1)

for i in 2:n + 1

Line 1,306:

Line 1,287:

83116//51639 is the 123456789-th term of the sequence.

</pre>

=={{header|Little Man Computer}}==

Runs in a home-made simulator, which is mostly compatible with Peter Higginson's online simulator. Only, for better control of the output format, I've added an instruction OTX (extended output). To run the code in PH's simulator, replace OTX and its parameter with OUT and no parameter.

===Find first n terms===

// Little Man Computer, for Rosetta Code.

// Displays terms of Calkin-Wilf sequence up to the given index.

Line 1,429:

Line 1,409:

The numbers in part 2 of the task are too large for LMC, so the demo program just confirms the example, that 9/4 is the 35th term.

// Little Man Computer, for Rosetta Code.

// Calkin-Wilf sequence: displays index of term entered by user.

Line 1,501:

Line 1,481:

9/4<-35

</pre>

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

<syntaxhighlight lang=~~Mathematica~~>ClearAll[a]

<syntaxhighlight lang="mathematica">ClearAll[a]

a[1] = 1;

a[n_?(GreaterThan[1])] := a[n] = 1/(2 Floor[a[n - 1]] + 1 - a[n - 1])

Line 1,525:

Line 1,503:

<pre>{1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4, 1/5, 5/4, 4/7, 7/3, 3/8}

123456789</pre>

=={{header|Nim}}==

We ignored the standard module “rationals” which is slow and have rather defined a fraction as a tuple of two 32 bits unsigned integers (slightly faster than 64 bits signed integers and sufficient for this task). Moreover, we didn’t do operations on fractions and computed directly the numerator and denominator values at each step. The fractions built this way are irreducible (which avoids to compute a GCD which is a slow operation).

With these optimizations, the program runs in less than 1.3 s on our laptop.

<syntaxhighlight lang=~~Nim~~>type Fraction = tuple[num, den: uint32]

<syntaxhighlight lang="nim">type Fraction = tuple[num, den: uint32]

iterator calkinWilf(): Fraction =

Line 1,571:

Line 1,548:

The element 83116/51639 is at position 123456789 in the sequence.</pre>

=={{header|Pascal}}==

These programs were written in Free Pascal, using the Lazarus IDE and the Free Pascal compiler version 3.2.0. They are based on the Wikipedia article "Calkin-Wilf tree", rather than the algorithms in the task description.

program CWTerms;

Line 1,719:

Line 1,695:

20: 3/8

</pre>

program CWIndex;

Line 1,775:

Line 1,751:

Index of 83116/51639 is 123456789

</pre>

=={{header|Perl}}==

<syntaxhighlight lang=perl>use strict;

<syntaxhighlight lang="perl">use strict;

use warnings;

use feature qw(say state);

Line 1,817:

Line 1,792:

83116/51639 is at index: 123456789</pre>

=={{header|Phix}}==

with javascript_semantics

requires("1.0.0") -- (new even() builtin)

Line 1,937:

Line 1,911:

83116/51639 is the 123,456,789th term of the sequence.

</pre>

=={{header|Prolog}}==

% John Devou: 26-Nov-2021

Line 1,963:

Line 1,936:

X = 123456789.

</pre>

=={{header|Python}}==

<syntaxhighlight lang=python>from fractions import Fraction

<syntaxhighlight lang="python">from fractions import Fraction

from math import floor

from itertools import islice, groupby

Line 2,001:

Line 1,973:

83116/51639 is the 123_456_789'th term.</pre>

=={{header|Quackery}}==

<code>cf</code> is defined at [[Continued fraction/Arithmetic/Construct from rational number#Quackery]].

<syntaxhighlight lang=~~Quackery~~> [ $ "bigrat.qky" loadfile ] now!

<syntaxhighlight lang="quackery"> [ $ "bigrat.qky" loadfile ] now!

[ ' [ [ 1 1 ] ]

Line 2,043:

Line 2,014:

123456789</pre>

=={{header|Raku}}==

In Raku, arrays are indexed from 0. The Calkin-Wilf sequence does not have a term defined at 0.

Line 2,049:

Line 2,019:

This implementation includes a bogus undefined value at position 0, having the bogus first term shifts the indices up by one, making the ordinal position and index match. Useful due to how reversibility function works.

<syntaxhighlight lang=raku line>my @calkin-wilf = Any, 1, {1 / (.Int × 2 + 1 - $_)} … *;

<syntaxhighlight lang="raku" line>my @calkin-wilf = Any, 1, {1 / (.Int × 2 + 1 - $_)} … *;

# Rational to Calkin-Wilf index

Line 2,089:

Line 2,059:

83116/51639 is at index: 123456789</pre>

=={{header|REXX}}==

The meat of this REXX program was provided by Paul Kislanko.

<syntaxhighlight lang=rexx>/*REXX pgm finds the Nth value of the Calkin─Wilf sequence (which will be a fraction),*/

<syntaxhighlight lang="rexx">/*REXX pgm finds the Nth value of the Calkin─Wilf sequence (which will be a fraction),*/

/*────────────────────── or finds which sequence number contains a specified fraction). */

numeric digits 2000 /*be able to handle ginormic integers. */

Line 2,150:

Line 2,118:

for 83116/51639, the element number for the Calkin─Wilf sequence is: 123,456,789th

</pre>

=={{header|Ruby}}==

<syntaxhighlight lang=ruby>cw = Enumerator.new do |y|

<syntaxhighlight lang="ruby">cw = Enumerator.new do |y|

y << a = 1.to_r

loop { y << a = 1/(2*a.floor + 1 - a) }

Line 2,177:

Line 2,144:

123456789

</pre>

=={{header|Rust}}==

<syntaxhighlight lang=rust>// [dependencies]

<syntaxhighlight lang="rust">// [dependencies]

// num = "0.3"

Line 2,262:

Line 2,228:

'''Continued Fraction support'''

<syntaxhighlight lang=scheme>; Create a terminating Continued Fraction generator for the given rational number.

<syntaxhighlight lang="scheme">; Create a terminating Continued Fraction generator for the given rational number.

; Returns one term per call; returns #f when no more terms remaining.

(define make-continued-fraction-gen

Line 2,297:

Line 2,263:

cf))</syntaxhighlight>

'''Calkin-Wilf sequence'''

<syntaxhighlight lang=scheme>; Create a Calkin-Wilf sequence generator.

<syntaxhighlight lang="scheme">; Create a Calkin-Wilf sequence generator.

(define make-calkin-wilf-gen

(lambda ()

Line 2,333:

Line 2,299:

(encode-list-of-runs 0 1 (continued-fraction-list-enforce-odd-length! (rat->cf-list rat)))))</syntaxhighlight>

'''The Task'''

<syntaxhighlight lang=scheme>(let ((count 20)

<syntaxhighlight lang="scheme">(let ((count 20)

(cw (make-calkin-wilf-gen)))

(printf "~%First ~a terms of the Calkin-Wilf sequence:~%" count)

Line 2,373:

Line 2,339:

83116/51639 @ 123456789

</pre>

=={{header|Sidef}}==

<syntaxhighlight lang=ruby>func calkin_wilf(n) is cached {

<syntaxhighlight lang="ruby">func calkin_wilf(n) is cached {

return 1 if (n == 1)

1/(2*floor(__FUNC__(n-1)) + 1 - __FUNC__(n-1))

Line 2,403:

Line 2,368:

83116/51639 is at index: 123456789

</pre>

=={{header|Vlang}}==

{{trans|Go}}s.

<syntaxhighlight lang=vlang>import math.fractions

<syntaxhighlight lang="vlang">import math.fractions

import math

import strconv

Line 2,519:

Line 2,483:

83116/51639 is the 123,456,789th term of the sequence.

</pre>

=={{header|Wren}}==

<syntaxhighlight lang=ecmascript>import "/rat" for Rat

<syntaxhighlight lang="ecmascript">import "/rat" for Rat

import "/fmt" for Fmt, Conv