A360565 -id:A360565 - cp's OEIS frontend

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

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, 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, 6, 9, 10, 1, 5, 7, 11, 1, 2, 6, 7, 8, 11, 12, 1, 3, 3, 7, 4, 9, 11

Offset: 1

Glen Whitney, Feb 11 2023

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.
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.

			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, ...).

Glen Whitney, Table of n, a(n) for n = 1..10052
G. Gordon and G. Whitney, The Playground Problem 367, Math Horizons, Vol. 26 No. 1 (2018), 32-33.

Denominators in A360565.
Level sizes of the tree in A360566.
See also the Farey tree in A007305 and A007306.
Cf. A293247.

from fractions import Fraction
row = [Fraction(1,2)]
seen = set([Fraction(1,2), Fraction(1,1)])
limit = 25 # chosen to generate 10000 fractions
nums = []
denoms = []
rowsizes = []
while row[0].denominator <= limit:
   rowsizes.append(len(row))
   newrow = []
   for frac in row:
      nums.append(frac.numerator)
      denoms.append(frac.denominator)
      for nf in [Fraction(frac.numerator, frac.denominator+1),
                 Fraction(frac.numerator+1, frac.denominator)]:
         if not(nf in seen):
            newrow.append(nf)
            seen.add(nf)
   row = newrow
print(', '.join(str(num) for num in nums))
print(', '.join(str(denom) for denom in denoms))
print(', '.join(str(rowsize) for rowsize in rowsizes))

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

Original entry on oeis.org

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, 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, 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

Offset: 3

Glen Whitney, Feb 11 2023

nonn

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

			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:
1/2
 |
1/3
 | \
1/4 2/3
 |
1/5
 | \
1/6 2/5
 |   |
1/7 3/5
 | \   \
1/8 2/7 4/5
Therefore, this sequence begins 1, 1, 2, 1, 2, 2, 3, ...

Glen Whitney, Table of n, a(n) for n = 3..10002
G. Gordon and G. Whitney, The Playground Problem 367, Math Horizons, Vol. 26 No. 1 (2018), 32-33.

Numerators and denominators of the nodes in A360564 and A360565.

See also the Farey tree in A007305 and A007306.

Python
```
# See the entry for A360564.
```

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python