login
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
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).
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
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
KEYWORD
nonn,tabf
AUTHOR
N. J. A. Sloane, Nov 21 2017
STATUS
approved