Anonymous user
Calkin-Wilf sequence: Difference between revisions
no edit summary
(add RPL) |
imported>Maxima enthusiast No edit summary |
||
Line 1,770:
<pre>{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, 3/8}
123456789</pre>
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">
/* 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)),
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(%);
</syntaxhighlight>
{{out}}
<pre>
[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,3/8]
123456789
</pre>
=={{header|Nim}}==
We ignored the standard module “rationals” which is slow and have rather defined a fraction as a tuple of two 32 bits unsigned integers (slightly faster than 64 bits signed integers and sufficient for this task). Moreover, we didn’t do operations on fractions and computed directly the numerator and denominator values at each step. The fractions built this way are irreducible (which avoids to compute a GCD which is a slow operation).
| |||