A360566 - OEIS

%I #17 Feb 15 2023 15:36:30

%S 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 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 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 Level sizes of numerator-denominator-incrementing tree of rationals in (0,1).

%C 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 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 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 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 For a proof that the tree described above includes all rational numbers between 0 and 1, see Gordon and Whitney.

%H Glen Whitney, <a href="/A360566/b360566.txt">Table of n, a(n) for n = 3..10002</a>

%H 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 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 1/2

%e  |

%e 1/3

%e  | \

%e 1/4 2/3

%e  |

%e 1/5

%e  | \

%e 1/6 2/5

%e  |   |

%e 1/7 3/5

%e  | \   \

%e 1/8 2/7 4/5

%e Therefore, this sequence begins 1, 1, 2, 1, 2, 2, 3, ...

%o (Python) # See the entry for A360564.

%Y Numerators and denominators of the nodes in A360564 and A360565.

%Y See also the Farey tree in A007305 and A007306.

%K nonn

%O 3,3

%A _Glen Whitney_, Feb 11 2023