Calkin-Wilf sequence: Difference between revisions

{{trans|Nim}}

n = 1

d = 1

L cw() != (83116, 51639)

index++

{{out}}

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

)

END

{{out}}

<pre>

=={{header|AppleScript}}==

on CalkinWilfSequence(n)

script o

set AppleScript's text item delimiters to astid

set output to output & (linefeed & "83116/51639 is term number " & positionResult)

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

=={{header|Arturo}}==

d: new 1

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

print ""

{{out}}

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

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

Sim ← { # Simplify a fraction

cnt‿fr:

fr ≢ 83116‿51639

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

)

& out$(get-term-num$83116/51639)

{{out}}

<pre>1/2

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

{{libheader|Boost}}

#include <vector>

#include <boost/rational.hpp>

rational r(83116, 51639);

std::cout << r << " is the " << term_number(r) << "th term of the sequence.\n";

{{out}}

===Find first n terms===

{{trans|Pascal}}

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

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

P F [enter with acc = 0]

[end]

{{out}}

<pre>

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

E 19 Z [relative address of entry point]

P F [enter with acc = 0]

{{out}}

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

{{out}}

<pre>

</pre>

; Indexof 83116/51639

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

{{out}}

<pre>

=={{header|Factor}}==

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

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

sequences strings vectors ;

20 calkin-wilf ltake [ pprint bl ] leach nl nl

{{out}}

<pre>

{{works with|gforth|0.7.3}}

: frac. swap . ." / " . ;

20 cw-seq

cr 83116 51639 2dup frac. cw-index index @ . ;

{{out}}

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

type rational

q.num = 83116

q.den = 51639

{{out}}

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

tn := getTermNumber(cf)

fmt.Printf("%s is the %sth term of the sequence.\n", r.RatString(), commatize(tn))

{{out}}

=={{header|Haskell}}==

import Data.Bool (bool)

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

"\n%s is at index %d of the Calkin-Wilf sequence.\n"

(show r)

{{out}}

<pre>

</pre>

given definitions

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

NB. base 2 @ reverse @ the cf's representation copies of 1 0 1 0 ...

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

=={{header|Julia}}==

{{trans|Wren}}

cw = zeros(Rational, n + 1)

for i in 2:n + 1

const tn = term_number(cf)

println("$r is the $tn-th term of the sequence.")

<pre>

The first 20 terms of the Calkin-Wilf sequence are: Rational[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]

===Find first n terms===

{{trans|Pascal}}

// Little Man Computer, for Rosetta Code.

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

b DAT

// end

{{out}}

<pre>

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

index DAT

// end

{{out}}

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

Break[];

]

{{out}}

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

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

iterator calkinWilf(): Fraction =

inc index

if an == Target: break

{{out}}

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

WriteLn( SysUtils.Format( '%8d: %d/%d', [k, Num, Den]));

end.

{{out}}

<pre>

20: 3/8

</pre>

program CWIndex;

end;

end.

{{out}}

<pre>

{{trans|Raku}}

{{libheader|ntheory}}

use warnings;

use feature qw(say state);

say 'First twenty terms of the Calkin-Wilf sequence:';

printf "%s ", $calkin_wilf->next() for 1..20;

{{out}}

<pre>First twenty terms of the Calkin-Wilf sequence:

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

<span style="color: #004080;">integer</span> <span style="color: #000000;">tn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_term_number</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cf</span><span style="color: #0000FF;">)</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;">"%d/%d is the %,d%s term of the sequence.\n"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">&{</span><span style="color: #000000;">tn</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">ord</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tn</span><span style="color: #0000FF;">)})</span>

{{out}}

<pre>

=={{header|Prolog}}==

% John Devou: 26-Nov-2021

t(A/B,S,C,X):- B > 1, divmod(A,B,M,N), T is 1-S, D is C*2**M, t(B/N,T,D,Y), X is Y + S*C*(2**M-1).

t(A/B,X):- t(A/B,1,1,X), !.

{{out}}

<pre>

=={{header|Python}}==

from math import floor

from itertools import islice, groupby

print('TERMS 1..20: ', ', '.join(str(x) for x in islice(cw(), 20)))

x = Fraction(83116, 51639)

{{out}}

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

[ ' [ [ 1 1 ] ]

[ do vulgar$ echo$ sp ]

cr cr

{{out}}

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

return $num.numerator if $num.denominator == 1;

$num.nude.join: '/';

{{out}}

<pre>First twenty terms of the Calkin-Wilf sequence: 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

=={{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. */

obin= copies(1, f1)copies(0, f0)obin

end /*until*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

=={{header|Ruby}}==

{{trans|Python}}

y << a = 1.to_r

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

puts cw.take(20).join(", ")

puts term_num (83116/51639r)

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

123456789

=={{header|Rust}}==

// num = "0.3"

let r = Rational::new(83116, 51639);

println!("{} is the {}th term of the sequence.", r, term_number(&r));

{{out}}

{{works with|Chez Scheme}}

'''Continued Fraction support'''

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

(define make-continued-fraction-gen

(set-car! cf-last-cons (1- (car cf-last-cons)))

(set-cdr! cf-last-cons (cons 1 '()))))

'''Calkin-Wilf sequence'''

(define make-calkin-wilf-gen

(lambda ()

; Return the run-length binary encoding from the odd-length Calkin-Wilf sequence of the

; given rational number. This is equal to the number's position in the sequence.

'''The Task'''

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

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

(printf "~a @ ~a~%" num (calkin-wilf-position num)))

(let ((num 83116/51639))

{{out}}

<pre>

=={{header|Sidef}}==

return 1 if (n == 1)

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

with (83116/51639) {|r|

say ("\n#{r.as_rat} is at index: ", r2cw(r))

{{out}}

<pre>

=={{header|Vlang}}==

{{trans|Go}}s.

import math

import strconv

tn := get_term_number(cf) or {0}

println("$r is the ${commatize(tn)}th term of the sequence.")

{{out}}

{{libheader|Wren-rat}}

{{libheader|Wren-fmt}}

import "/fmt" for Fmt, Conv

var cf = toContinued.call(r)

var tn = getTermNumber.call(cf)

{{out}}