cp's OEIS Frontend

A360566 Level sizes of numerator-denominator-incrementing tree of rationals in (0,1).

%I A360566 #17 Feb 15 2023 15:36:30
%S A360566 1,1,2,1,2,2,3,2,4,2,4,4,3,3,6,3,6,4,5,5,8,4,7,7,7,5,10,4,8,8,11,8,11,
%T A360566 6,12,12,11,6,12,7,12,10,14,10,18,7,12,12,13,11,20,9,14,11,15,13,22,8,
%U A360566 16,18,17,14,19,9,18,14,19,12,24,11,22,22,19,15,24,12,24,18,27,22,36,12,19,23
%N A360566 Level sizes of numerator-denominator-incrementing tree of rationals in (0,1).
%C A360566 Construct a tree of rational numbers by starting with a root labeled 1/2. Then iteratively add children to each node as follows: to the node labeled p/q in lowest terms, add children labeled with any of p/(q+1) and (p+1)/q that are less than one and have not already appeared in the tree. Then a(n) is the number of nodes n-3 levels below the root (the offset 3 is chosen so that the level number corresponds to the sum of the numerator and denominator of most fractions at level n).
%C A360566 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.
%C A360566 It might appear at first glance that the sum of the numerator and denominator of all fractions at level n divides n. However, 7/10 and 8/9 first appear at level 33 (as children of 7/9 at level 32), but 17 does not divide 33.
%C A360566 Since 1/(n-1) always appears on level n, a(n) > 0. Bertrand's postulate implies that for all n > 5, a(n) > 1, since for each prime p with n/2 < p < n, (n+1-p)/p will also occur at level n.
%C A360566 For a proof that the tree described above includes all rational numbers between 0 and 1, see Gordon and Whitney.
%H A360566 Glen Whitney, <a href="/A360566/b360566.txt">Table of n, a(n) for n = 3..10002</a>
%H A360566 G. Gordon and G. Whitney, <a href="https://www.jstor.org/stable/48664225">The Playground Problem 367</a>, Math Horizons, Vol. 26 No. 1 (2018), 32-33.
%e A360566 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. Continuing in this fashion, the first few levels of the tree look like:
%e A360566 1/2
%e A360566  |
%e A360566 1/3
%e A360566  | \
%e A360566 1/4 2/3
%e A360566  |
%e A360566 1/5
%e A360566  | \
%e A360566 1/6 2/5
%e A360566  |   |
%e A360566 1/7 3/5
%e A360566  | \   \
%e A360566 1/8 2/7 4/5
%e A360566 Therefore, this sequence begins 1, 1, 2, 1, 2, 2, 3, ...
%o A360566 (Python) # See the entry for A360564.
%Y A360566 Numerators and denominators of the nodes in A360564 and A360565.
%Y A360566 See also the Farey tree in A007305 and A007306.
%K A360566 nonn
%O A360566 3,3
%A A360566 _Glen Whitney_, Feb 11 2023