login
A360565
Denominators of breadth-first numerator-denominator-incrementing enumeration of rationals in (0,1).
3
2, 3, 4, 3, 5, 6, 5, 7, 5, 8, 7, 5, 9, 7, 10, 9, 8, 7, 11, 7, 12, 11, 8, 7, 13, 11, 9, 4, 14, 13, 11, 15, 13, 11, 16, 15, 14, 13, 12, 11, 17, 13, 11, 18, 17, 14, 13, 12, 11, 19, 17, 13, 11, 20, 19, 17, 13, 11, 21, 19, 17, 13, 6, 22, 21, 20, 19, 18, 17, 14, 13, 23, 19, 17, 13, 24, 23, 19, 18, 17, 14, 13, 25, 23, 10, 19, 9, 17, 15
OFFSET
1,1
COMMENTS
Construct a tree of rational numbers by starting with a root labeled 1/2. Then iteratively add children to each node breadth-first as follows: to the node labeled p/q in lowest terms, add children labeled with any of p/(q+1) and (p+1)/q (in that order) that are less than one and have not already appeared in the tree. Then a(n) is the denominator of the n-th rational number (in lowest terms) added to the tree.
This construction is similar to the Farey tree except that the children of p/q are its mediants with 0/1 and 1/0 (if those mediants have not already occurred), rather than its mediants with its nearest neighbors among its ancestors.
For a proof that the tree described above includes all rational numbers between 0 and 1, see Gordon and Whitney.
LINKS
G. Gordon and G. Whitney, The Playground Problem 367, Math Horizons, Vol. 26 No. 1 (2018), 32-33.
EXAMPLE
To build the tree, 1/2 only has child 1/3, since 2/2 = 1 is outside of (0,1). Then 1/3 has children 1/4 and 2/3. In turn, 1/4 only has child 1/5 because 2/4 = 1/2 has already occurred, and 2/3 has no children because 2/4 has already occurred and 3/3 is too large. Thus, the sequence begins 2, 3, 4, 3, 5, ... (the denominators of 1/2, 1/3, 1/4, 2/3, 1/5, ...).
PROG
(Python) # See the entry for A360564.
CROSSREFS
Numerators in A360564.
Level sizes of the tree in A360566.
See also the Farey tree in A007305 and A007306.
Cf. A293248.
Sequence in context: A325277 A257573 A182973 * A278056 A366880 A324345
KEYWORD
frac,nonn,tabf,look
AUTHOR
Glen Whitney, Feb 11 2023
STATUS
approved