|
|
A360564
|
|
Numerators of breadth-first numerator-denominator-incrementing enumeration of rationals in (0,1).
|
|
3
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
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 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.
|
|
LINKS
|
|
|
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 1, 1, 1, 2, 1, ... (the numerators of 1/2, 1/3, 1/4, 2/3, 1/5, ...).
|
|
PROG
|
(Python)
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))
|
|
CROSSREFS
|
Level sizes of the tree in A360566.
|
|
KEYWORD
|
frac,nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|