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

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, 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, 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

Offset: 0

Author

N. J. A. Sloane, Nov 21 2017

Keywords

• nonn
• tabf

Comments

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

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

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

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

Examples

			This version of the tree begins as follows:
.................0/1..1/1
...............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
...
With the fractions written as pairs, the first few rows are:
[[0, 1], [1, 1]],
[[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]],
[[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]]
...
		

References

• W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
• See A007305, A007306, A049455, A049456, etc. for many other references and links about the tree of Farey fractions (of which there are many versions).

Links

• Index entries for fraction trees

Crossrefs

Cf. A007305, A007306, A049455, A049456.

See A294442 for Kepler's tree of fractions.

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

Programs

Maple

# S[n] is the list of fractions, written as pairs [i, j], in row n of the triangle of Farey fractions
S[0]:=[[0, 1], [1, 1]];
for n from 1 to 6 do
S[n]:=[[0,1]];
for k from 1 to nops(S[n-1])-1 do
a:=S[n-1][k][1]+S[n-1][k+1][1];
b:=S[n-1][k][2]+S[n-1][k+1][2];
S[n]:=[op(S[n]), [a, b], S[n-1][k+1]];
od:
lprint(S[n]);
od: