How to resolve the algorithm Calkin-Wilf sequence step by step in the Wren programming language

Published on 12 May 2024 09:40 PM
#Wren

How to resolve the algorithm Calkin-Wilf sequence step by step in the Wren programming language

Table of Contents

Problem Statement

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

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

It is also possible, given a non-negative 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:

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.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Calkin-Wilf sequence step by step in the Wren programming language

Source code in the wren programming language

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)

You may also check:How to resolve the algorithm Roman numerals/Decode step by step in the Prolog programming language
You may also check:How to resolve the algorithm Fibonacci sequence step by step in the Comefrom0x10 programming language
You may also check:How to resolve the algorithm Window creation step by step in the Scheme programming language
You may also check:How to resolve the algorithm Middle three digits step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Write float arrays to a text file step by step in the Ada programming language