cp's OEIS Frontend

A360564 Numerators of breadth-first numerator-denominator-incrementing enumeration of rationals in (0,1).

%I A360564 #18 Feb 12 2023 10:00:34
%S A360564 1,1,1,2,1,1,2,1,3,1,2,4,1,3,1,2,3,4,1,5,1,2,5,6,1,3,5,3,1,2,4,1,3,5,
%T A360564 1,2,3,4,5,6,1,5,7,1,2,5,6,7,8,1,3,7,9,1,2,4,8,10,1,3,5,9,5,1,2,3,4,5,
%U A360564 6,9,10,1,5,7,11,1,2,6,7,8,11,12,1,3,3,7,4,9,11
%N A360564 Numerators of breadth-first numerator-denominator-incrementing enumeration of rationals in (0,1).
%C A360564 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 numerator of the n-th rational number (in lowest terms) added to the tree.
%C A360564 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 A360564 For a proof that the tree described above includes all rational numbers between 0 and 1, see Gordon and Whitney.
%H A360564 Glen Whitney, <a href="/A360564/b360564.txt">Table of n, a(n) for n = 1..10052</a>
%H A360564 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 A360564 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 1, 1, 1, 2, 1, ... (the numerators of 1/2, 1/3, 1/4, 2/3, 1/5, ...).
%o A360564 (Python)
%o A360564 from fractions import Fraction
%o A360564 row = [Fraction(1,2)]
%o A360564 seen = set([Fraction(1,2), Fraction(1,1)])
%o A360564 limit = 25 # chosen to generate 10000 fractions
%o A360564 nums = []
%o A360564 denoms = []
%o A360564 rowsizes = []
%o A360564 while row[0].denominator <= limit:
%o A360564    rowsizes.append(len(row))
%o A360564    newrow = []
%o A360564    for frac in row:
%o A360564       nums.append(frac.numerator)
%o A360564       denoms.append(frac.denominator)
%o A360564       for nf in [Fraction(frac.numerator, frac.denominator+1),
%o A360564                  Fraction(frac.numerator+1, frac.denominator)]:
%o A360564          if not(nf in seen):
%o A360564             newrow.append(nf)
%o A360564             seen.add(nf)
%o A360564    row = newrow
%o A360564 print(', '.join(str(num) for num in nums))
%o A360564 print(', '.join(str(denom) for denom in denoms))
%o A360564 print(', '.join(str(rowsize) for rowsize in rowsizes))
%Y A360564 Denominators in A360565.
%Y A360564 Level sizes of the tree in A360566.
%Y A360564 See also the Farey tree in A007305 and A007306.
%Y A360564 Cf. A293247.
%K A360564 frac,nonn,tabf
%O A360564 1,4
%A A360564 _Glen Whitney_, Feb 11 2023