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

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.

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

Table of n, a(n) for n=0..104.

Index entries for fraction trees

Example

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

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:

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.

Sequence in context: A217605 A096651 A209354 * A318163 A114640 A056890

Adjacent sequences: A294443 A294444 A294445 * A294447 A294448 A294449

Keyword

nonn,tabf

Author

N. J. A. Sloane, Nov 21 2017

Status

approved