A293248 -id:A293248 - cp's OEIS frontend

A293247 Let S be the sequence of rational numbers generated by these rules: 1 is in S, and if u/v is in S (with gcd(u, v) = 1), then (u+1)/v and u/(v+1) are in S, and duplicates are deleted as they occur; a(n) = the numerator of the n-th term of S.

1, 2, 1, 3, 1, 4, 3, 2, 1, 5, 1, 6, 5, 2, 1, 7, 5, 3, 1, 8, 7, 5, 4, 2, 1, 9, 7, 3, 1, 10, 9, 8, 7, 4, 3, 2, 1, 11, 7, 5, 1, 12, 11, 8, 7, 6, 5, 2, 1, 13, 11, 9, 4, 3, 5, 3, 1, 14, 13, 11, 4, 2, 1, 15, 13, 11, 5, 3, 1, 16, 15, 14, 13, 12, 11, 6, 5, 4, 3, 2, 1

Offset: 1

Rémy Sigrist, Oct 03 2017

See A293248 for the corresponding denominators.
The sequence S is a "rational" variant of A232559.
If r appears in S, then 1/r appears in S.
S is a permutation of the positive rational numbers:
- let f be the function u/v -> (u+1)/v
  and g be the function u/v -> u/(v+1),
- let h^k be the k-th iterate of h,
- let r = u/v be a rational number in reduced form,
- without loss of generality, we can assume that u > v,
- according to Dirichlet's theorem on arithmetic progressions, we can choose a prime number p = k*u - 1 > u (where k > 2),
- we also have k*u - 1 > k*v,
- f^(p-1)(1) = p,
- g^(k*v-1)(f^(p-1)(1)) = p / (k*v) (and gcd(p, k*v)=1),
- f(g^(k*v-1)(f^(p-1)(1))) = (p+1) / (k*v) = (k*u) / (k*v) = u/v = r, QED.

			S(1) = 1 by definition; so a(1) = 1.
(1+1)/1 = 2 has not yet occurred; so S(2) = 2 and a(2) = 2.
1/(1+1) = 1/2 has not yet occurred; so S(3) = 1/2 and a(3) = 1.
(2+1)/1 = 3 has not yet occurred; so S(4) = 3 and a(4) = 3.
2/(1+1) = 1 has already occurred.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Wikipedia, Dirichlet's theorem on arithmetic progressions
Rémy Sigrist, Colorized scatterplot of A293247 vs. A293248 for n=1..100000
Rémy Sigrist, PARI program for A293247

Cf. A232559, A293248.

PARI
```
See Links section.
```

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

Original entry on oeis.org

2, 3, 4, 3, 5, 6, 5, 7, 5, 8, 7, 5, 9, 7, 10, 9, 8, 7, 11, 7, 12, 11, 8, 7, 13, 11, 9, 4, 14, 13, 11, 15, 13, 11, 16, 15, 14, 13, 12, 11, 17, 13, 11, 18, 17, 14, 13, 12, 11, 19, 17, 13, 11, 20, 19, 17, 13, 11, 21, 19, 17, 13, 6, 22, 21, 20, 19, 18, 17, 14, 13, 23, 19, 17, 13, 24, 23, 19, 18, 17, 14, 13, 25, 23, 10, 19, 9, 17, 15

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 denominator 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 2, 3, 4, 3, 5, ... (the denominators 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.

Numerators in A360564.
Level sizes of the tree in A360566.
See also the Farey tree in A007305 and A007306.
Cf. A293248.

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

cp's OEIS Frontend

A293247 Let S be the sequence of rational numbers generated by these rules: 1 is in S, and if u/v is in S (with gcd(u, v) = 1), then (u+1)/v and u/(v+1) are in S, and duplicates are deleted as they occur; a(n) = the numerator of the n-th term of S.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI