# runs of bits and Continued Fractions

Wouter Meeussen eu000949 at pophost.eunet.be
Fri Apr 23 21:59:12 CEST 1999

```a nice one-to-one relation between integers and fractions :

write the integer as "binary", (always starts with "1"),
count the runs of identical bits, and form them into a list :
{1,1,1,0,0,1} becomes {3,2,1} for 3 ones, 2 naughts and a one.
increase the last counter by one, in exemplo {3,2,2},  [cfr remark 1],
finally make this list into a continued fraction 3 +1/(2 +1/(2) )

the inverse is evidently:
write the fraction as a continued fraction, (never ends with "1")
decrease the last element of the resulting list with one,
then, starting with ones, build a list of 3 ones, 2 naughts and a one ;
finally convert the binary to an integer.
-----------------------------------------
[remark 1] :
if a Cont.Fr. ends with a one, it collapses :
p+1/                 p+1/
/q+1/   becomes      / (q+1)
/1

without adding 1 to the trailing element, the relation would not be one-to-one.
-----------------------------------------
the integers 1 to 17 are converted into:
{2, 3/2, 3, 4/3, 5/3, 5/2, 4, 5/4, 7/5, 8/5, 7/4, 7/3, 8/3, 7/2,
5, 6/5, 9/7}

The numerators of CFruns[n] for n upto 128 are:
A007306=Denominators of Farey (or Stern-Brocot) tree fractions.

{2,3,3,4,5,5,4,5,7,8,7,7,8,7,5,6,9,11,10,11,13,12,9,9,12,13,11,10,11,9,6,7,11,
14,13,15,18,17,13,14,19,21,18,17,19,16,11,11,16,19,17,18,21,19,14,13,17,18,
15,13,14,11,7,8,13,17,16,19,23,22,17,19,26,29,25,24,27,23,16,17,25,30,27,29,
34,31,23,22,29,31,26,23,25,20,13,13,20,25,23,26,31,29,22,23,31,34,29,27,30,
25,17,16,23,27,24,25,29,26,19,17,22,23,19,16,17,13,8,9}

and the denominators are: (I am sorry, but the terms
5,4,3,3,2,1,5,7,8,7,7,8,7,5,4,5,5,4 do not match anything in the table.)

{1,2,1,3,3,2,1,4,5,5,4,3,3,2,1,5,7,8,7,7,8,7,5,4,5,5,4,3,3,2,1,6,9,11,10,11,
13,12,9,9,12,13,11,10,11,9,6,5,7,8,7,7,8,7,5,4,5,5,4,3,3,2,1,7,11,14,13,15,
18,17,13,14,19,21,18,17,19,16,11,11,16,19,17,18,21,19,14,13,17,18,15,13,14,
11,7,6,9,11,10,11,13,12,9,9,12,13,11,10,11,9,6,5,7,8,7,7,8,7,5,4,5,5,4,3,3,
2,1,8}

-----------------------------------------
for archive:

Needs["NumberTheory`ContinuedFractions`"]

CFruns[n_Integer]:=
Fold[#2+1/#1&,\[Infinity],
Reverse[MapAt[#+1&,Length/@Split[IntegerDigits[n,2]],{-1}]]]

inverseCFruns[n:( _Rational|_Integer)]:=
FromDigits[
Flatten[MapIndexed[Table[(1 +(-1)^First[#2+1])/2,{#1}] &,
MapAt[#-1&,Flatten[{First[ContinuedFraction[n]]}],{-1}]]],2]

-----------------------------------------

wouter.

ID Number: A007305 (Formerly M0113)
Sequence:
1,1,2,1,2,3,3,1,2,3,3,4,5,5,4,1,2,3,3,4,5,5,4,5,7,8,7,7,8,7,5,1,2,3,3,
4,5,5,4,5,7,8,7,7,8,7,5,6,9,11,10,11,13,12,9,9,12,13,11,10,11,9,6
,1,2,
3,3,4,5,5,4,5,7,8,7,7,8,7,5,6,9,11,10,11,13,12,9,9,12,13,11
Name:      Numerators of Farey (or Stern-Brocot) tree fractions.
References J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of
S. A. Burr, ed., The
Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl.
Math., 46 (1992).
Amer. Math. Soc.
Example:   1/2; 1/3, 2/3; 1/4, 2/5, 3/5, 3/4; 1/5, 2/7, 3/8, 3/7, 4/7, 5/8,
5/7, 4/5;...
Keywords:  nonn,frac,tabl,nice
Offset:    1
Author(s): njas

ID Number: A007306 (Formerly M0437)
Sequence:
2,3,3,4,5,5,4,5,7,8,7,7,8,7,5,6,9,11,10,11,13,12,9,9,12,13,11,10,11,9,
6,7,11,14,13,15,18,17,13,14,19,21,18,17,19,16,11,11,16,19,17,18,2
1,19,
14,13,17,18,15,13,14,11,7,8,13,17,16,19,23,22,17,19
Name:      Denominators of Farey (or Stern-Brocot) tree fractions.
References J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of
S. A. Burr, ed., The
Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl.
Math., 46 (1992).
Amer. Math. Soc.
Example:   1/2; 1/3, 2/3; 1/4, 2/5, 3/5, 3/4; 1/5, 2/7, 3/8, 3/7, 4/7, 5/8,
5/7, 4/5;...
Keywords:  nonn,frac,tabl,nice
Offset:    1
Author(s): njas

I am sorry, but the terms
5,4,3,3,2,1,5,7,8,7,7,8,7,5,4,5,5,4
do not match anything in the table.
Dr. Wouter L. J. MEEUSSEN
w.meeussen.vdmcc at vandemoortele.be
eu000949 at pophost.eunet.be

```