Calkin-Wilf sequence
The Calkin-Wilf sequence contains every nonnegative rational number exactly once. It can be calculated recursively as follows:
a0 = 0
an+1 = 1/(2⌊an⌋+1-an) for n > 0
- Show on this page terms 0 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
- Wikipedia entry: Calkin-Wilf tree
FreeBASIC
Uses the code from Greatest common divisor#FreeBASIC as an include.
<lang freebasic>#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 = 0 q.den = 1 for i as integer = 0 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."</lang>
- Output:
0 0 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.
Raku
Technically, the Calkin-Wilf sequence should begin with 1, but start with 0 as that is what the task requires. <lang perl6>my @calkin-wilf = 0, 1, {( 1 / (.Int × 2 + 1 - $_)).FatRat} … *;
- 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[^20]».&prat.join: ', ';
say "\n99,991st through 100,000th: ",
@calkin-wilf[99_990 .. 99_999]».&prat.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: '/';
}</lang>
- Output:
First twenty terms of the Calkin-Wilf sequence: 0, 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 99,991st through 100,000th: 782/1085, 1085/303, 303/1036, 1036/733, 733/1163, 1163/430, 430/987, 987/557, 557/684, 684/127 83116/51639 is at index: 123456789