A350391 The largest denominator that can be made from n repeated applications of the maps f(x) = x + 1 or g(x) = -1/x, starting from 0.

1, 1, 1, 2, 3, 4, 5, 6, 8, 11, 15, 19, 24, 30, 41, 56, 72, 91, 115, 153, 209, 269, 345, 436, 571, 780, 1005, 1292, 1653, 2131, 2911, 3751, 4827, 6191, 7953, 10864, 14000, 18034, 23184, 29681, 40545, 52249, 67320, 86617, 111097, 151316, 194997

Offset: 0

Author

Peter Kagey, Jan 10 2022

Keywords

• nonn

Comments

Every rational number can be generated by repeated applications of the maps f(x) = x + 1 and g(x) = -1/x.

For n > 0, a(n) is the maximum entry in row n of A226247.

Examples

			For n = 0, a(0) = 1 because  0/1 = 0.
For n = 1, a(1) = 1 because  1/1 = f(0).
For n = 2, a(2) = 1 because  2/1 = f(f(0)).
For n = 3, a(3) = 2 because -1/2 = g(f(f(0))).
For n = 4, a(4) = 3 because -1/3 = g(f(f(f(0)))).
For n = 5, a(5) = 4 because -1/4 = g(f(f(f(f(0))))).
For n = 6, a(6) = 5 because -1/5 = g(f(f(f(f(f(0)))))).
For n = 7, a(7) = 6 because -1/6 = g(f(f(f(f(f(f(0))))))).
For n = 8, a(8) = 8 because -3/8 = g(f(f(f(g(f(f(f(0)))))))).
		

Links

• Code Golf Stack Exchange, Iterate your way to a fraction.
• Tom Davis, Conway's Rational Tangles.

Crossrefs

Cf. A226247, A226248, A226249, A226250.

Programs

Python

from fractions import Fraction
from itertools import count, islice
def agen():
    rats = {Fraction(0, 1)}
    for n in count(1):
        yield max(r.denominator for r in rats)
        newrats = set()
        for r in rats:
            newrats.add(1+r)
            if r != 0:
                newrats.add(-1/r)
        rats = newrats
print(list(islice(agen(), 25))) # Michael S. Branicky, Jan 17 2022

Extensions

a(42)-a(46) from Michael S. Branicky, Jan 17 2022