require "rat"
local fmt = require "fmt"

local function calkin_wilf(n)
    local cw = {}
    cw[1] = rat.of(1)
    for i = 2, n do
        local t = cw[i - 1]:floor() * 2 - cw[i - 1] + 1
        cw[i] = cw[1] / t
    end
    return cw
end

local function to_continued(r)
    local a = r:getNum()
    local b = r:getDen()
    local res = {}
    repeat
        res:insert(math.floor(a / b))
        a, b = b, a % b
    until a == 1

    if #res % 2 == 0 then  -- ensure always odd
        res[#res] -= 1
        res:insert(1)
    end
    return res
end

local function get_term_number(cf)
    local b = ""
    local d = "1"
    for cf as n do
        b = string.rep(d, n) .. b
        d = (d == "1") ? "0" : "1"
    end
    return tonumber(b, 2)
end

local cw = calkin_wilf(20)
print("The first 20 terms of the Calkin-Wilf sequence are:")
for i = 1, 20 do fmt.print("%2d: %s", i, cw[i]:format("%d", "%d", false)) end
print()
local r = rat.of(83116, 51639)
local cf = to_continued(r)
local tn = get_term_number(cf)
fmt.print("%s is the %s term of the sequence.", r, fmt.ord(tn, true))