Calkin-Wilf sequence: Difference between revisions

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

<br><br>

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

{{trans|Nim}}

 

n = 1

d = 1

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.

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

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

Position of 83116/51639 in the sequence: 123456789

</pre>

=={{header|AppleScript}}==

on CalkinWilfSequence(n)

script o

 

{{output}}

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

 

d: new 1

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

 

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.

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

 

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

Sim ← { # Simplify a fraction

fr ≢ 83116‿51639

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

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

{{trans|Python}}

& 0:?i

& whl

3/8

123456789</pre>

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

{{libheader|Boost}}

#include <vector>

#include <boost/rational.hpp>

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

</pre>

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

===Find first n terms===

{{trans|Pascal}}

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

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

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

{{trans|Pascal}}

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

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

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

===The Tasks===

; first 20

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

</syntaxhighlight>

</pre>

; Indexof 83116/51639

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

</syntaxhighlight>

=={{header|Factor}}==

{{works with|Factor|0.99 2020-08-14}}

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

sequences strings vectors ;

83116/51639 is at index 123456789.

</pre>

=={{header|Forth}}==

 

{{works with|gforth|0.7.3}}

 

 

: frac. swap . ." / " . ;

3 / 8

83116 / 51639 123456789 ok</pre>

=={{header|FreeBASIC}}==

 

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

 

 

type rational

20 3/8

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

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

 

 

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

{{trans|Wren}}

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.

 

import (

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

</pre>

=={{header|Haskell}}==

import Data.Bool (bool)

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

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

</pre>

=={{header|J}}==

<pre>

</pre>

given definitions

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

 

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

</syntaxhighlight>

=={{header|Julia}}==

{{trans|Wren}}

cw = zeros(Rational, n + 1)

for i in 2:n + 1

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

{{trans|Pascal}}

// Little Man Computer, for Rosetta Code.

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

{{trans|Pascal}}

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.

9/4<-35

</pre>

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

a[1] = 1;

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

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

 

 

iterator calkinWilf(): Fraction =

 

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;

 

20: 3/8

</pre>

program CWIndex;

 

Index of 83116/51639 is 123456789

</pre>

=={{header|Perl}}==

{{trans|Raku}}

{{libheader|ntheory}}

use warnings;

use feature qw(say state);

 

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

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.0"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (new even() builtin)</span>

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

</pre>

=={{header|Prolog}}==

% John Devou: 26-Nov-2021

 

X = 123456789.

</pre>

=={{header|Python}}==

from math import floor

from itertools import islice, groupby

 

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

 

 

[ ' [ [ 1 1 ] ]

 

123456789</pre>

=={{header|Raku}}==

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

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.

 

 

# Rational to Calkin-Wilf index

 

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

=={{header|REXX}}==

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

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

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

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

</pre>

=={{header|Ruby}}==

{{trans|Python}}

y << a = 1.to_r

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

123456789

</pre>

=={{header|Rust}}==

// num = "0.3"

 

{{works with|Chez Scheme}}

'''Continued Fraction support'''

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

(define make-continued-fraction-gen

cf))</syntaxhighlight>

'''Calkin-Wilf sequence'''

(define make-calkin-wilf-gen

(lambda ()

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

'''The Task'''

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

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

83116/51639 @ 123456789

</pre>

=={{header|Sidef}}==

return 1 if (n == 1)

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

83116/51639 is at index: 123456789

</pre>

=={{header|Vlang}}==

{{trans|Go}}s.

import math

import strconv

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

</pre>

=={{header|Wren}}==

{{libheader|Wren-rat}}

{{libheader|Wren-fmt}}

import "/fmt" for Fmt, Conv