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.
Links: More info
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;...
See also: Cf. A007306.
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.
Links: More info
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;...
See also: Cf. A007305.
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
More information about the SeqFan
mailing list