25 lines
963 B
Text
25 lines
963 B
Text
/* The function fusc is related to Calkin-Wilf sequence */
|
|
fusc(n):=block(
|
|
[k:n,a:1,b:0],
|
|
while k>0 do (if evenp(k) then (k:k/2,a:a+b) else (k:(k-1)/2,b:a+b)),
|
|
b)$
|
|
|
|
/* Calkin-Wilf function using fusc */
|
|
calkin_wilf(n):=fusc(n)/fusc(n+1)$
|
|
|
|
/* Function that given a nonnegative rational returns its position in the Calkin-Wilf sequence */
|
|
cf_bin(fracti):=block(
|
|
cf_list:cf(fracti),
|
|
cf_len:length(cf_list),
|
|
if oddp(cf_len) then cf_list:reverse(cf_list) else cf_list:reverse(append(at(cf_list,[cf_list[cf_len]=cf_list[cf_len]-1]),[1])),
|
|
makelist(lambda([x],if oddp(x) then makelist(1,j,1,cf_list[x]) else makelist(0,j,1,cf_list[x]))(i),i,1,length(cf_list)), /* decoding part begins here */
|
|
apply(append,%%),
|
|
apply("+",makelist(2^i,i,0,length(%%)-1)*reverse(%%)))$
|
|
|
|
/* Test cases */
|
|
/* 20 first terms of the sequence */
|
|
makelist(calkin_wilf(i),i,1,20);
|
|
|
|
/* Position of 83116/51639 in Calkin-Wilf sequence */
|
|
83116/51639$
|
|
cf_bin(%);
|