Re Adam Goucher's neat summary --- Aboreally speaking, does "Calkin-Wilf" = "Stern-Brocot" ? And (same paragraph) who is "Newnham" ? I think we should be told ... WFL On 11/20/15, Bill Gosper <billgosper@gmail.com> wrote:
See https://cp4space.wordpress.com/2013/10/24/enumerating-the-rationals/ Here's a fast implementation of this forward and backward Wilf-Calkin map that NeilB did in Mathematica. In[345]:= newman2pos[71426/7623] // tim
During evaluation of In[345]:= 0.001112,0
Out[345]= 999999999
In[347]:= pos2newman[67107847] // tim
During evaluation of In[347]:= 0.000729,0
Out[347]= 355/113
calkinwilf[num_, denom_] := Block[{lis = {}, n = num, d = denom}, (While[ n > 1 || d > 1, (lis = Prepend[lis, Boole[n > d]]; If[n > d, n -= d, d -= n])]; lis)];
wilfcalkin[bitlis_List] := Block[{n = 1, d = 1}, (Do[ If[bitlis[[i]] == 0, d += n, n += d], {i, 1, Length[bitlis]}]; Rational[n, d])]
newman2pos[num_, denom_] := FromDigits[Prepend[calkinwilf[num, denom], 1], 2]; newman2pos[frac_] := newman2pos[Numerator[frac], Denominator[frac]]
pos2newman[0] = 0; pos2newman[pos_] := Sign[pos]*wilfcalkin[IntegerDigits[pos, 2][[2 ;; -1]]] --rwg _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun