I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Calkin-Wilf sequence

From Rosetta Code
Task
Calkin-Wilf sequence
You are encouraged to solve this task according to the task description, using any language you may know.

The Calkin-Wilf sequence contains every nonnegative rational number exactly once. It can be calculated recursively as follows:

a1 = 1

an+1 = 1/(2⌊an⌋+1-an) for n > 1

  • Show on this page terms 1 through 20 of the Calkin-Wilf sequence.

To avoid floating point error, you may want to use a rational number data type.


It is also possible, given a nonnegative rational number, to determine where it appears in the sequence without calculating the sequence. The procedure is to get the continued fraction representation of the rational and use it as the run-length encoding of the binary representation of the term number, beginning from the end of the continued fraction. It only works if the number of terms in the continued fraction is odd- use either of the two equivalent representations to achieve this:

[a0; a1, a2, ..., an] = [a0; a1, a2 ,..., an-1, 1]

Thus, for example, the fraction 9/4 has odd continued fraction representation 2; 3, 1, giving a binary representation of 100011, which means 9/4 appears as the 35th term of the sequence.

  • Find the position of the number 83116/51639 in the Calkin-Wilf sequence.
See also


AppleScript[edit]

-- Return the first n terms of the sequence. Tree generation. Faster for this purpose.
on CalkinWilfSequence(n)
script o
property sequence : {{1, 1}} -- Initialised with the first term ({numerator, denominator}).
end script
 
-- Work through the growing sequence list, adding the two children of each term to the end and
-- converting each term to text representing the vulgar fraction. Stop adding children halfway through.
set halfway to n div 2
repeat with position from 1 to n
set {numerator, denominator} to item position of o's sequence
if (position ≤ halfway) then
tell numerator + denominator
set end of o's sequence to {numerator, it}
if ((position < halfway) or (position * 2 < n)) then set end of o's sequence to {it, denominator}
end tell
end if
set item position of o's sequence to (numerator as text) & "/" & denominator
end repeat
 
return o's sequence
end CalkinWilfSequence
 
-- Alternatively, return terms pos1 to pos2. Binary run-length encoding. Doesn't need to work from the beginning of the sequence.
on CalkinWilfSequence2(pos1, pos2)
script o
property sequence : {}
end script
 
repeat with position from pos1 to pos2
-- Build a continued fraction list from the binary run-length encoding of this position index.
-- There's no need to put the last value into the list as it's used immediately.
set continuedFraction to {}
set bitValue to 1
set runLength to 0
repeat until (position = 0)
if (position mod 2 = bitValue) then
set runLength to runLength + 1
else
set end of continuedFraction to runLength
set bitValue to (bitValue + 1) mod 2
set runLength to 1
end if
set position to position div 2
end repeat
-- Work out the numerator and denominator from the continued fraction and derive text representing the vulgar fraction.
set numerator to runLength
set denominator to 1
repeat with i from (count continuedFraction) to 1 by -1
tell numerator
set numerator to numerator * (item i of continuedFraction) + denominator
set denominator to it
end tell
end repeat
set end of o's sequence to (numerator as text) & "/" & denominator
end repeat
 
return o's sequence
end CalkinWilfSequence2
 
-- Return the sequence position of the term with the given numerator and denominator.
on CalkinWilfSequencePosition(numerator, denominator)
-- Build a continued fraction list from the input.
set continuedFraction to {}
repeat until (denominator is 0)
set end of continuedFraction to numerator div denominator
set {numerator, denominator} to {denominator, numerator mod denominator}
end repeat
-- If it has an even number of entries, convert to the equivalent odd number.
if ((count continuedFraction) mod 2 is 0) then
set last item of continuedFraction to (last item of continuedFraction) - 1
set end of continuedFraction to 1
end if
-- "Binary run-length decode" the entries to get the position index.
set position to 0
set bitValue to 1
repeat with i from (count continuedFraction) to 1 by -1
repeat (item i of continuedFraction) times
set position to position * 2 + bitValue
end repeat
set bitValue to (bitValue + 1) mod 2
end repeat
 
return position
end CalkinWilfSequencePosition
 
-- Task code:
local sequenceResult1, sequenceResult2, positionResult, output, astid
set sequenceResult1 to CalkinWilfSequence(20)
set sequenceResult2 to CalkinWilfSequence2(1, 20)
set positionResult to CalkinWilfSequencePosition(83116, 51639)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to ", "
set output to "First twenty terms of sequence using tree generation:" & (linefeed & sequenceResult1)
set output to output & (linefeed & "Ditto using binary run-length encoding:") & (linefeed & sequenceResult1)
set AppleScript's text item delimiters to astid
set output to output & (linefeed & "83116/51639 is term number " & positionResult)
return output
Output:
"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"

C++[edit]

Library: Boost
#include <iostream>
#include <vector>
#include <boost/rational.hpp>
 
using rational = boost::rational<unsigned long>;
 
unsigned long floor(const rational& r) {
return r.numerator()/r.denominator();
}
 
rational calkin_wilf_next(const rational& term) {
return 1UL/(2UL * floor(term) + 1UL - term);
}
 
std::vector<unsigned long> continued_fraction(const rational& r) {
unsigned long a = r.numerator();
unsigned long b = r.denominator();
std::vector<unsigned long> result;
do {
result.push_back(a/b);
unsigned long c = a;
a = b;
b = c % b;
} while (a != 1);
if (result.size() > 0 && result.size() % 2 == 0) {
--result.back();
result.push_back(1);
}
return result;
}
 
unsigned long term_number(const rational& r) {
unsigned long result = 0;
unsigned long d = 1;
unsigned long p = 0;
for (unsigned long n : continued_fraction(r)) {
for (unsigned long i = 0; i < n; ++i, ++p)
result |= (d << p);
d = !d;
}
return result;
}
 
int main() {
rational term = 1;
std::cout << "First 20 terms of the Calkin-Wilf sequence are:\n";
for (int i = 1; i <= 20; ++i) {
std::cout << std::setw(2) << i << ": " << term << '\n';
term = calkin_wilf_next(term);
}
rational r(83116, 51639);
std::cout << r << " is the " << term_number(r) << "th term of the sequence.\n";
}
Output:
First 20 terms of the Calkin-Wilf sequence are:
 1: 1/1
 2: 1/2
 3: 2/1
 4: 1/3
 5: 3/2
 6: 2/3
 7: 3/1
 8: 1/4
 9: 4/3
10: 3/5
11: 5/2
12: 2/5
13: 5/3
14: 3/4
15: 4/1
16: 1/5
17: 5/4
18: 4/7
19: 7/3
20: 3/8
83116/51639 is the 123456789th term of the sequence.

F#[edit]

The Function[edit]

 
// 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[edit]

first 20
 
cW |> Seq.take 20 |> Seq.iter(fun(n,g)->printf "%d/%d " n g);printfn ""
 
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
Indexof 83116/51639
 
printfn "%d" (1+Seq.findIndex(fun n->n=(83116,51639)) cW)
 
Output:
123456789

Factor[edit]

Works with: Factor version 0.99 2020-08-14
USING: formatting io kernel lists lists.lazy math
math.continued-fractions math.functions math.parser prettyprint
sequences strings vectors ;
 
: next-cw ( x -- y ) [ floor dup + ] [ 1 swap - + recip ] bi ;
 
: calkin-wilf ( -- list ) 1 [ next-cw ] lfrom-by ;
 
: >continued-fraction ( x -- seq )
1vector [ dup last integer? ] [ dup next-approx ] until
dup length even? [ unclip-last 1 - suffix! 1 suffix! ] when ;
 
: cw-index ( x -- n )
>continued-fraction <reversed>
[ even? CHAR: 1 CHAR: 0 ? <string> ] map-index concat bin> ;
 
! Task
"First 20 terms of the Calkin-Wilf sequence:" print
20 calkin-wilf ltake [ pprint bl ] leach nl nl
 
83116/51639 cw-index "83116/51639 is at index %d.\n" printf
Output:
First 20 terms of the Calkin-Wilf sequence:
1 1/2 2 1/3 1+1/2 2/3 3 1/4 1+1/3 3/5 2+1/2 2/5 1+2/3 3/4 4 1/5 1+1/4 4/7 2+1/3 3/8 

83116/51639 is at index 123456789.

FreeBASIC[edit]

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

#include "gcd.bas"
 
type rational
num as integer
den as integer
end type
 
dim shared as rational ONE, TWO
ONE.num = 1 : ONE.den = 1
TWO.num = 2 : TWO.den = 1
 
function simplify( byval a as rational ) as rational
dim as uinteger g = gcd( a.num, a.den )
a.num /= g : a.den /= g
if a.den < 0 then
a.den = -a.den
a.num = -a.num
end if
return a
end function
 
operator + ( a as rational, b as rational ) as rational
dim as rational ret
ret.num = a.num * b.den + b.num*a.den
ret.den = a.den * b.den
return simplify(ret)
end operator
 
operator - ( a as rational, b as rational ) as rational
dim as rational ret
ret.num = a.num * b.den - b.num*a.den
ret.den = a.den * b.den
return simplify(ret)
end operator
 
operator * ( a as rational, b as rational ) as rational
dim as rational ret
ret.num = a.num * b.num
ret.den = a.den * b.den
return simplify(ret)
end operator
 
operator / ( a as rational, b as rational ) as rational
dim as rational ret
ret.num = a.num * b.den
ret.den = a.den * b.num
return simplify(ret)
end operator
 
function floor( a as rational ) as rational
dim as rational ret
ret.den = 1
ret.num = a.num \ a.den
return ret
end function
 
function cw_nextterm( q as rational ) as rational
dim as rational ret = (TWO*floor(q))
ret = ret + ONE : ret = ret - q
return ONE / ret
end function
 
function frac_to_int( byval a as rational ) as uinteger
redim as uinteger cfrac(-1)
dim as integer lt = -1, ones = 1, ret = 0
do
lt += 1
redim preserve as uinteger cfrac(0 to lt)
cfrac(lt) = floor(a).num
a = a - floor(a) : a = ONE / a
loop until a.num = 0 or a.den = 0
if lt mod 2 = 1 and cfrac(lt) = 1 then
lt -= 1
cfrac(lt)+=1
redim preserve as uinteger cfrac(0 to lt)
end if
if lt mod 2 = 1 and cfrac(lt) > 1 then
cfrac(lt) -= 1
lt += 1
redim preserve as uinteger cfrac(0 to lt)
cfrac(lt) = 1
end if
for i as integer = lt to 0 step -1
for j as integer = 1 to cfrac(i)
ret *= 2
if ones = 1 then ret += 1
next j
ones = 1 - ones
next i
return ret
end function
 
function disp_rational( a as rational ) as string
if a.den = 1 or a.num= 0 then return str(a.num)
return str(a.num)+"/"+str(a.den)
end function
 
dim as rational q
q.num = 1
q.den = 1
for i as integer = 1 to 20
print i, disp_rational(q)
q = cw_nextterm(q)
next i
 
q.num = 83116
q.den = 51639
print disp_rational(q)+" is the "+str(frac_to_int(q))+"th term."
Output:
 1            1
 2            1/2
 3            2
 4            1/3
 5            3/2
 6            2/3
 7            3
 8            1/4
 9            4/3
 10           3/5
 11           5/2
 12           2/5
 13           5/3
 14           3/4
 15           4
 16           1/5
 17           5/4
 18           4/7
 19           7/3
 20           3/8
83116/51639 is the 123456789th term.

Go[edit]

Translation of: 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.

package main
 
import (
"fmt"
"math"
"math/big"
"strconv"
"strings"
)
 
func calkinWilf(n int) []*big.Rat {
cw := make([]*big.Rat, n+1)
cw[0] = big.NewRat(1, 1)
one := big.NewRat(1, 1)
two := big.NewRat(2, 1)
for i := 1; i < n; i++ {
t := new(big.Rat).Set(cw[i-1])
f, _ := t.Float64()
f = math.Floor(f)
t.SetFloat64(f)
t.Mul(t, two)
t.Sub(t, cw[i-1])
t.Add(t, one)
t.Inv(t)
cw[i] = new(big.Rat).Set(t)
}
return cw
}
 
func toContinued(r *big.Rat) []int {
a := r.Num().Int64()
b := r.Denom().Int64()
var res []int
for {
res = append(res, int(a/b))
t := a % b
a, b = b, t
if a == 1 {
break
}
}
le := len(res)
if le%2 == 0 { // ensure always odd
res[le-1]--
res = append(res, 1)
}
return res
}
 
func getTermNumber(cf []int) int {
b := ""
d := "1"
for _, n := range cf {
b = strings.Repeat(d, n) + b
if d == "1" {
d = "0"
} else {
d = "1"
}
}
i, _ := strconv.ParseInt(b, 2, 64)
return int(i)
}
 
func commatize(n int) string {
s := fmt.Sprintf("%d", n)
if n < 0 {
s = s[1:]
}
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
if n >= 0 {
return s
}
return "-" + s
}
 
func main() {
cw := calkinWilf(20)
fmt.Println("The first 20 terms of the Calkin-Wilf sequnence are:")
for i := 1; i <= 20; i++ {
fmt.Printf("%2d: %s\n", i, cw[i-1].RatString())
}
fmt.Println()
r := big.NewRat(83116, 51639)
cf := toContinued(r)
tn := getTermNumber(cf)
fmt.Printf("%s is the %sth term of the sequence.\n", r.RatString(), commatize(tn))
}
Output:
The first 20 terms of the Calkin-Wilf sequnence are:
 1: 1
 2: 1/2
 3: 2
 4: 1/3
 5: 3/2
 6: 2/3
 7: 3
 8: 1/4
 9: 4/3
10: 3/5
11: 5/2
12: 2/5
13: 5/3
14: 3/4
15: 4
16: 1/5
17: 5/4
18: 4/7
19: 7/3
20: 3/8

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

Haskell[edit]

import Control.Monad (forM_)
import Data.Bool (bool)
import Data.List.NonEmpty (NonEmpty, fromList, toList, unfoldr)
import Text.Printf (printf)
 
-- The infinite Calkin-Wilf sequence, a(n), starting with a(1) = 1.
calkinWilfs :: [Rational]
calkinWilfs = iterate (recip . succ . ((-) =<< (2 *) . fromIntegral . floor)) 1
 
-- The index into the Calkin-Wilf sequence of a given rational number, starting
-- with 1 at index 1.
calkinWilfIdx :: Rational -> Integer
calkinWilfIdx = rld . cfo
 
-- A continued fraction representation of a given rational number, guaranteed
-- to have an odd length.
cfo :: Rational -> NonEmpty Int
cfo = oddLen . cf
 
-- The canonical (i.e. shortest) continued fraction representation of a given
-- rational number.
cf :: Rational -> NonEmpty Int
cf = unfoldr step
where
step r =
case properFraction r of
(n, 1) -> (succ n, Nothing)
(n, 0) -> (n, Nothing)
(n, f) -> (n, Just (recip f))
 
-- Ensure a continued fraction has an odd length.
oddLen :: NonEmpty Int -> NonEmpty Int
oddLen = fromList . go . toList
where
go [x, y] = [x, pred y, 1]
go (x:y:zs) = x : y : go zs
go xs = xs
 
-- Run-length decode a continued fraction.
rld :: NonEmpty Int -> Integer
rld = snd . foldr step (True, 0)
where
step i (b, n) =
let p = 2 ^ i
in (not b, n * p + bool 0 (pred p) b)
 
main :: IO ()
main = do
forM_ (take 20 $ zip [1 :: Int ..] calkinWilfs) $
\(i, r) -> printf "%2d  %s\n" i (show r)
let r = 83116 / 51639
printf
"\n%s is at index %d of the Calkin-Wilf sequence.\n"
(show r)
(calkinWilfIdx r)
Output:
 1  1 % 1
 2  1 % 2
 3  2 % 1
 4  1 % 3
 5  3 % 2
 6  2 % 3
 7  3 % 1
 8  1 % 4
 9  4 % 3
10  3 % 5
11  5 % 2
12  2 % 5
13  5 % 3
14  3 % 4
15  4 % 1
16  1 % 5
17  5 % 4
18  4 % 7
19  7 % 3
20  3 % 8

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

Julia[edit]

Translation of: Wren
function calkin_wilf(n)
cw = zeros(Rational, n + 1)
for i in 2:n + 1
t = Int(floor(cw[i - 1])) * 2 - cw[i - 1] + 1
cw[i] = 1 // t
end
return cw[2:end]
end
 
function continued(r::Rational)
a, b = r.num, r.den
res = []
while true
push!(res, Int(floor(a / b)))
a, b = b, a % b
a == 1 && break
end
return res
end
 
function term_number(cf)
b, d = "", "1"
for n in cf
b = d^n * b
d = (d == "1") ? "0" : "1"
end
return parse(Int, b, base=2)
end
 
const cw = calkin_wilf(20)
println("The first 20 terms of the Calkin-Wilf sequence are: $cw")
 
const r = 83116 // 51639
const cf = continued(r)
const tn = term_number(cf)
println("$r is the $tn-th term of the sequence.")
 
Output:
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]
83116//51639 is the 123456789-th term of the sequence.

Phix[edit]

function calkin_wilf(integer len)
sequence cw = repeat(0,len)
integer n=0, d=1
for i=1 to len do
{n,d} = {d,(floor(n/d)*2+1)*d-n}
cw[i] = {n,d}
end for
return cw
end function
 
function to_continued_fraction(sequence r)
integer {a,b} = r
sequence res = {}
while true do
res &= floor(a/b)
{a, b} = {b, remainder(a,b)}
if a=1 then exit end if
end while
return res
end function
 
function get_term_number(sequence cf)
sequence b = {}
integer d = 1
for i=1 to length(cf) do
b &= repeat(d,cf[i])
d = 1-d
end for
return bits_to_int(b)
end function
 
-- additional verification methods (2 of)
function i_to_cf(integer i)
-- sequence b = trim_tail(int_to_bits(i,32),0)&2,
sequence b = int_to_bits(i)&2,
cf = iff(b[1]=0?{0}:{})
while length(b)>1 do
for j=2 to length(b) do
if b[j]!=b[1] then
cf &= j-1
b = b[j..$]
exit
end if
end for
end while
-- replace even length with odd length equivalent:
if remainder(length(cf),2)=0 then
cf[$] -= 1
cf &= 1
end if
return cf
end function
 
function cf2r(sequence cf)
integer n=0, d=1
for i=length(cf) to 2 by -1 do
{n,d} = {d,n+d*cf[i]}
end for
return {n+cf[1]*d,d}
end function
 
function prettyr(sequence r)
integer {n,d} = r
return iff(d=1?sprintf("%d",n):sprintf("%d/%d",{n,d}))
end function
 
sequence cw = calkin_wilf(20)
printf(1,"The first 20 terms of the Calkin-Wilf sequence are:\n")
for i=1 to 20 do
string s = prettyr(cw[i]),
r = prettyr(cf2r(i_to_cf(i)))
integer t = get_term_number(to_continued_fraction(cw[i]))
printf(1,"%2d: %-4s [==> %2d: %-3s]\n", {i, s, t, r})
end for
printf(1,"\n")
sequence r = {83116,51639}
sequence cf = to_continued_fraction(r)
integer tn = get_term_number(cf)
printf(1,"%d/%d is the %,d%s term of the sequence.\n", r&{tn,ord(tn)})
Output:
The first 20 terms of the Calkin-Wilf sequence are:
 1: 1    [==>  1: 1  ]
 2: 1/2  [==>  2: 1/2]
 3: 2    [==>  3: 2  ]
 4: 1/3  [==>  4: 1/3]
 5: 3/2  [==>  5: 3/2]
 6: 2/3  [==>  6: 2/3]
 7: 3    [==>  7: 3  ]
 8: 1/4  [==>  8: 1/4]
 9: 4/3  [==>  9: 4/3]
10: 3/5  [==> 10: 3/5]
11: 5/2  [==> 11: 5/2]
12: 2/5  [==> 12: 2/5]
13: 5/3  [==> 13: 5/3]
14: 3/4  [==> 14: 3/4]
15: 4    [==> 15: 4  ]
16: 1/5  [==> 16: 1/5]
17: 5/4  [==> 17: 5/4]
18: 4/7  [==> 18: 4/7]
19: 7/3  [==> 19: 7/3]
20: 3/8  [==> 20: 3/8]

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

Python[edit]

from fractions import Fraction
from math import floor
from itertools import islice, groupby
 
 
def cw():
a = Fraction(1)
while True:
yield a
a = 1 / (2 * floor(a) + 1 - a)
 
def r2cf(rational):
num, den = rational.numerator, rational.denominator
while den:
num, (digit, den) = den, divmod(num, den)
yield digit
 
def get_term_num(rational):
ans, dig, pwr = 0, 1, 0
for n in r2cf(rational):
for _ in range(n):
ans |= dig << pwr
pwr += 1
dig ^= 1
return ans
 
 
if __name__ == '__main__':
print('TERMS 1..20: ', ', '.join(str(x) for x in islice(cw(), 20)))
x = Fraction(83116, 51639)
print(f"\n{x} is the {get_term_num(x):_}'th term.")
Output:
TERMS 1..20:  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

83116/51639 is the 123_456_789'th term.

Raku[edit]

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.

my @calkin-wilf = Any, 1, {1 / (.Int × 2 + 1 - $_)}*;
 
# Rational to Calkin-Wilf index
sub r2cw (Rat $rat) { :2( join '', flat (flat (1,0) xx *) Zxx reverse r2cf $rat ) }
 
# The task
 
say "First twenty terms of the Calkin-Wilf sequence: ",
@calkin-wilf[1..20]».&prat.join: ', ';
 
say "\n99991st through 100000th: ",
(my @tests = @calkin-wilf[99_991 .. 100_000])».&prat.join: ', ';
 
say "\nCheck reversibility: ", @tests».Rat».&r2cw.join: ', ';
 
say "\n83116/51639 is at index: ", r2cw 83116/51639;
 
 
# Helper subs
sub r2cf (Rat $rat is copy) { # Rational to continued fraction
gather loop {
$rat -= take $rat.floor;
last if !$rat;
$rat = 1 / $rat;
}
}
 
sub prat ($num) { # pretty Rat
return $num unless $num ~~ Rat|FatRat;
return $num.numerator if $num.denominator == 1;
$num.nude.join: '/';
}
Output:
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

99991st through 100000th: 1085/303, 303/1036, 1036/733, 733/1163, 1163/430, 430/987, 987/557, 557/684, 684/127, 127/713

Check reversibility: 99991, 99992, 99993, 99994, 99995, 99996, 99997, 99998, 99999, 100000

83116/51639 is at index: 123456789

Rust[edit]

// [dependencies]
// num = "0.3"
 
use num::rational::Rational;
 
fn calkin_wilf_next(term: &Rational) -> Rational {
Rational::from_integer(1) / (Rational::from_integer(2) * term.floor() + 1 - term)
}
 
fn continued_fraction(r: &Rational) -> Vec<isize> {
let mut a = *r.numer();
let mut b = *r.denom();
let mut result = Vec::new();
loop {
let (q, r) = num::integer::div_rem(a, b);
result.push(q);
a = b;
b = r;
if a == 1 {
break;
}
}
let len = result.len();
if len != 0 && len % 2 == 0 {
result[len - 1] -= 1;
result.push(1);
}
result
}
 
fn term_number(r: &Rational) -> usize {
let mut result: usize = 0;
let mut d: usize = 1;
let mut p: usize = 0;
for n in continued_fraction(r) {
for _ in 0..n {
result |= d << p;
p += 1;
}
d ^= 1;
}
result
}
 
fn main() {
println!("First 20 terms of the Calkin-Wilf sequence are:");
let mut term = Rational::from_integer(1);
for i in 1..=20 {
println!("{:2}: {}", i, term);
term = calkin_wilf_next(&term);
}
let r = Rational::new(83116, 51639);
println!("{} is the {}th term of the sequence.", r, term_number(&r));
}
Output:
First 20 terms of the Calkin-Wilf sequence are:
 1: 1
 2: 1/2
 3: 2
 4: 1/3
 5: 3/2
 6: 2/3
 7: 3
 8: 1/4
 9: 4/3
10: 3/5
11: 5/2
12: 2/5
13: 5/3
14: 3/4
15: 4
16: 1/5
17: 5/4
18: 4/7
19: 7/3
20: 3/8
83116/51639 is the 123456789th term of the sequence.

Wren[edit]

Library: Wren-rat
Library: Wren-fmt
import "/rat" for Rat
import "/fmt" for Fmt, Conv
 
var calkinWilf = Fn.new { |n|
var cw = List.filled(n, null)
cw[0] = Rat.one
for (i in 1...n) {
var t = cw[i-1].floor * 2 - cw[i-1] + 1
cw[i] = Rat.one / t
}
return cw
}
 
var toContinued = Fn.new { |r|
var a = r.num
var b = r.den
var res = []
while (true) {
res.add((a/b).floor)
var t = a % b
a = b
b = t
if (a == 1) break
}
if (res.count%2 == 0) { // ensure always odd
res[-1] = res[-1] - 1
res.add(1)
}
return res
}
 
var getTermNumber = Fn.new { |cf|
var b = ""
var d = "1"
for (n in cf) {
b = (d * n) + b
d = (d == "1") ? "0" : "1"
}
return Conv.atoi(b, 2)
}
 
var cw = calkinWilf.call(20)
System.print("The first 20 terms of the Calkin-Wilf sequence are:")
Rat.showAsInt = true
for (i in 1..20) Fmt.print("$2d: $s", i, cw[i-1])
System.print()
var r = Rat.new(83116, 51639)
var cf = toContinued.call(r)
var tn = getTermNumber.call(cf)
Fmt.print("$s is the $,r term of the sequence.", r, tn)
Output:
The first 20 terms of the Calkin-Wilf sequence are:
 1: 1
 2: 1/2
 3: 2
 4: 1/3
 5: 3/2
 6: 2/3
 7: 3
 8: 1/4
 9: 4/3
10: 3/5
11: 5/2
12: 2/5
13: 5/3
14: 3/4
15: 4
16: 1/5
17: 5/4
18: 4/7
19: 7/3
20: 3/8

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