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 



Task part 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 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:

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



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.



Task part 2

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


See also

 Wikipedia entry: Calkin-Wilf tree
 Continued fraction
 Continued fraction/Arithmetic/Construct from rational number


with javascript_semantics
requires("1.0.0")   -- (new even() builtin)

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 odd_length(sequence cf)
    -- replace even length continued fraction with odd length equivalent
--  if remainder(length(cf),2)=0 then
    if even(length(cf)) then
        cf[$] -= 1
        cf &= 1
    end if
    return cf
end function
 
function to_continued_fraction(sequence r)
    integer {a,b} = r
    sequence cf = {}
    while true do
        cf &= floor(a/b)
        {a, b} = {b, remainder(a,b)}
        if a=1 then exit end if
    end while
    cf = odd_length(cf)
    return cf
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
    integer t = bits_to_int(b)
    return t
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
    cf = odd_length(cf)
    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)})
