1. Broken rosettacode entry
- Posted by petelomax Jun 26, 2021
- 1226 views
The https://rosettacode.org/wiki/Calkin-Wilf_sequence#Phix entry was not working, specifically get_term_number() was not returning the expected 1..20.
I managed to fix it by factoring out a new odd_length() routine, and have updated the above entry.
However, I am a bit confused as to how it ever worked, and no longer appear to have whatever old version of Phix it (allegedly!) once worked on.
I have tried 0.8.3, 0.8.2, and 0.8.1, and afaict we are only talking 7/12/2020, about 7 months ago at the earliest. Maybe I just posted the wrong code.
I know I have fairly recently tweaked int_to_bits() to make the second (nbits) parameter optional for positive values (see the older commented out call in the code below).
If anyone finds this works on some old version of Phix they still have knocking about, please let me know.
Here is the previous (broken) version
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 to_continued_fraction(sequence r) integer {a,b} = r sequence res = {} while true do res &= floor(a/b) {a, b} = {b, remainder(a,b)} if a=1 then exit end if end while return res 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 return bits_to_int(b) 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 -- replace even length with odd length equivalent: if remainder(length(cf),2)=0 then cf[$] -= 1 cf &= 1 end if 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 21 terms of the Calkin-Wilf sequence are:\n 0: 0\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)})
Desired output
The first 20 terms of the Calkin-Wilf sequence are: 1: 1 [==> 1: 1 ] 2: 1/2 [==> 2: 1/2] 3: 2 [==> 3: 2 ] 4: 1/3 [==> 4: 1/3] 5: 3/2 [==> 5: 3/2] 6: 2/3 [==> 6: 2/3] 7: 3 [==> 7: 3 ] 8: 1/4 [==> 8: 1/4] 9: 4/3 [==> 9: 4/3] 10: 3/5 [==> 10: 3/5] 11: 5/2 [==> 11: 5/2] 12: 2/5 [==> 12: 2/5] 13: 5/3 [==> 13: 5/3] 14: 3/4 [==> 14: 3/4] 15: 4 [==> 15: 4 ] 16: 1/5 [==> 16: 1/5] 17: 5/4 [==> 17: 5/4] 18: 4/7 [==> 18: 4/7] 19: 7/3 [==> 19: 7/3] 20: 3/8 [==> 20: 3/8] 83116/51639 is the 123,456,789th term of the sequence.
Actual output
The first 20 terms of the Calkin-Wilf sequence are: 1: 1 [==> 1: 1 ] 2: 1/2 [==> 0: 1/2] 3: 2 [==> 3: 2 ] 4: 1/3 [==> 0: 1/3] 5: 3/2 [==> 1: 3/2] 6: 2/3 [==> 6: 2/3] 7: 3 [==> 7: 3 ] 8: 1/4 [==> 0: 1/4] 9: 4/3 [==> 1: 4/3] 10: 3/5 [==> 2: 3/5] 11: 5/2 [==> 3: 5/2] 12: 2/5 [==> 12: 2/5] 13: 5/3 [==> 13: 5/3] 14: 3/4 [==> 14: 3/4] 15: 4 [==> 15: 4 ] 16: 1/5 [==> 0: 1/5] 17: 5/4 [==> 1: 5/4] 18: 4/7 [==> 2: 4/7] 19: 7/3 [==> 3: 7/3] 20: 3/8 [==> 4: 3/8] 83116/51639 is the 123,456,789th term of the sequence.