cp's OEIS Frontend

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).

%I A294446 #18 Nov 21 2017 15:35:01
%S A294446 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 A294446 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 A294446 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 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).
%C A294446 The first row contains the fractions 0/1, 1/1,
%C A294446 and thereafter we copy the previous row, interpolating (a+c)/(b+d) between each pair of adjacent fractions a/b, c/d.
%C A294446 This version of the Farey tree contains the fractions in the range [0,1].
%C A294446 If we just look at the numerators we get A049455 and if we just look at the denominators we get A086596.
%D A294446 W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
%D A294446 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 A294446 <a href="/index/Fo#fraction_trees">Index entries for fraction trees</a>
%e A294446 This version of the tree begins as follows:
%e A294446 .................0/1..1/1
%e A294446 ...............0/1..1/2..1/1
%e A294446 ..........0/1..1/3..1/2..2/3..1/1
%e A294446 0/1..1/4..1/3..2/5..1/2..3/5..2/3..3/4..1/1
%e A294446 ...
%e A294446 With the fractions written as pairs, the first few rows are:
%e A294446 [[0, 1], [1, 1]],
%e A294446 [[0, 1], [1, 2], [1, 1]],
%e A294446 [[0, 1], [1, 3], [1, 2], [2, 3], [1, 1]],
%e A294446 [[0, 1], [1, 4], [1, 3], [2, 5], [1, 2], [3, 5], [2, 3], [3, 4], [1, 1]],
%e A294446 [[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 A294446 ...
%p A294446 # S[n] is the list of fractions, written as pairs [i, j], in row n of the triangle of Farey fractions
%p A294446 S[0]:=[[0, 1], [1, 1]];
%p A294446 for n from 1 to 6 do
%p A294446 S[n]:=[[0,1]];
%p A294446 for k from 1 to nops(S[n-1])-1 do
%p A294446 a:=S[n-1][k][1]+S[n-1][k+1][1];
%p A294446 b:=S[n-1][k][2]+S[n-1][k+1][2];
%p A294446 S[n]:=[op(S[n]), [a, b], S[n-1][k+1]];
%p A294446 od:
%p A294446 lprint(S[n]);
%p A294446 od:
%Y A294446 Cf. A007305, A007306, A049455, A049456.
%Y A294446 See A294442 for Kepler's tree of fractions.
%Y A294446 For the number of distinct numerators in row n, see A293165, and for the distinct denominators see A293160.
%K A294446 nonn,tabf
%O A294446 0,4
%A A294446 _N. J. A. Sloane_, Nov 21 2017