login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A294446 The tree of Farey fractions (or the Stern-Brocot tree), read across rows (the fraction i/j is represented as the pair i,j). 2

%I #18 Nov 21 2017 15:35:01

%S 0,1,1,2,1,1,0,1,1,3,1,2,2,3,1,1,0,1,1,4,1,3,2,5,1,2,3,5,2,3,3,4,1,1,

%T 0,1,1,5,1,4,2,7,1,3,3,8,2,5,3,7,1,2,4,7,3,5,5,8,2,3,5,7,3,4,4,5,1,1,

%U 0,1,1,6,1,5,2,9,1,4,3,11,2,7,3,10,1,3,4,11,3,8,5,13,2,5,5,12,3,7,4,9,1,2,5,9,4

%N The tree of Farey fractions (or the Stern-Brocot tree), read across rows (the fraction i/j is represented as the pair i,j).

%C The first row contains the fractions 0/1, 1/1,

%C and thereafter we copy the previous row, interpolating (a+c)/(b+d) between each pair of adjacent fractions a/b, c/d.

%C This version of the Farey tree contains the fractions in the range [0,1].

%C If we just look at the numerators we get A049455 and if we just look at the denominators we get A086596.

%D W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.

%D See A007305, A007306, A049455, A049456, etc. for many other references and links about the tree of Farey fractions (of which there are many versions).

%H <a href="/index/Fo#fraction_trees">Index entries for fraction trees</a>

%e This version of the tree begins as follows:

%e .................0/1..1/1

%e ...............0/1..1/2..1/1

%e ..........0/1..1/3..1/2..2/3..1/1

%e 0/1..1/4..1/3..2/5..1/2..3/5..2/3..3/4..1/1

%e ...

%e With the fractions written as pairs, the first few rows are:

%e [[0, 1], [1, 1]],

%e [[0, 1], [1, 2], [1, 1]],

%e [[0, 1], [1, 3], [1, 2], [2, 3], [1, 1]],

%e [[0, 1], [1, 4], [1, 3], [2, 5], [1, 2], [3, 5], [2, 3], [3, 4], [1, 1]],

%e [[0, 1], [1, 5], [1, 4], [2, 7], [1, 3], [3, 8], [2, 5], [3, 7], [1, 2], [4, 7,], [3, 5], [5, 8], [2, 3], [5, 7], [3, 4], [4, 5], [1, 1]]

%e ...

%p # S[n] is the list of fractions, written as pairs [i, j], in row n of the triangle of Farey fractions

%p S[0]:=[[0, 1], [1, 1]];

%p for n from 1 to 6 do

%p S[n]:=[[0,1]];

%p for k from 1 to nops(S[n-1])-1 do

%p a:=S[n-1][k][1]+S[n-1][k+1][1];

%p b:=S[n-1][k][2]+S[n-1][k+1][2];

%p S[n]:=[op(S[n]), [a, b], S[n-1][k+1]];

%p od:

%p lprint(S[n]);

%p od:

%Y Cf. A007305, A007306, A049455, A049456.

%Y See A294442 for Kepler's tree of fractions.

%Y For the number of distinct numerators in row n, see A293165, and for the distinct denominators see A293160.

%K nonn,tabf

%O 0,4

%A _N. J. A. Sloane_, Nov 21 2017

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 15:58 EDT 2024. Contains 371254 sequences. (Running on oeis4.)