OpenEuphoria

1. Broken rosettacode entry

• Posted by petelomax Jun 26, 2021
• 1090 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.