A226130 Denominators of rational numbers as generated by the rules: 1 is in S, and if nonzero x is in S, then x+1 and -1/x are in S. (See Comments.)

1, 1, 1, 1, 2, 1, 1, 3, 2, 1, 4, 3, 2, 1, 1, 5, 4, 3, 2, 2, 3, 1, 6, 5, 4, 3, 3, 5, 2, 5, 3, 1, 7, 6, 5, 4, 4, 7, 3, 8, 5, 2, 7, 5, 3, 1, 1, 8, 7, 6, 5, 5, 9, 4, 11, 7, 3, 11, 8, 5, 2, 2, 9, 7, 5, 3, 3, 4, 1, 9, 8, 7, 6, 6, 11, 5, 14, 9, 4, 15, 11, 7, 3, 3

Offset: 1

Author

Clark Kimberling, May 28 2013

Keywords

• nonn
• frac
• tabf

Comments

Let S be the set of numbers defined by these rules: 1 is in S, and if nonzero x is in S, then x + 1 and -1/x are in S. Then S is the set of all rational numbers, produced in generations as follows: g(1) = (1), g(2) = (2, -1), g(3) = (3, -1/2, 0), g(4) = (4, -1/3, 1/2), ... For n > 4, once g(n-1) = (c(1), ..., c(z)) is defined, g(n) is formed from the vector (c(1)+1, -1/c(1), c(2)+1, -1/c(2), ..., c(z)+1, -1/c(z)) by deleting previously generated elements. Let S' denote the sequence formed by concatenating the generations.

A226130: Denominators of terms of S'

A226131: Numerators of terms of S'

A226136: Positions of positive integers in S'

A226137: Positions of integers in S'

The length of row n is given by A226275(n-1). - Peter Kagey, Jan 17 2022

Examples

			The denominators and numerators are read from the rationals in S':
  1/1, 2/1, -1/1, 3/1, -1/2, 0/1, 4/1, -1/3, 1/2, ...
Table begins:
  n |
  --+-----------------------------------------------
  1 | 1;
  2 | 1, 1;
  3 | 1, 2, 1;
  4 | 1, 3, 2;
  5 | 1, 4, 3, 2, 1;
  6 | 1, 5, 4, 3, 2, 2, 3;
  7 | 1, 6, 5, 4, 3, 3, 5, 2, 5, 3;
  8 | 1, 7, 6, 5, 4, 4, 7, 3, 8, 5, 2, 7, 5, 3, 1;
		

Links

• Clark Kimberling, Table of n, a(n) for n = 1..1000
• Index entries for fraction trees

Crossrefs

Cf. A226080 (rabbit ordering of positive rationals).

Cf. A226130, A226131, A226136, A226137, A226275.

Cf. A226247 (analogous with "0 is in S").

Programs

Mathematica

g[1] := {1}; z = 20; g[n_] := g[n] = DeleteCases[Flatten[Transpose[{# + 1, -1/#}]]&[DeleteCases[g[n - 1], 0]], Apply[Alternatives, Flatten[Map[g, Range[n - 1]]]]]; Flatten[Map[g, Range[7]]]  (* ordered rationals *)
Map[g, Range[z]]; Table[Length[g[i]], {i, 1, z}] (* cf. A003410 *)
f = Flatten[Map[g, Range[z]]];
Take[Denominator[f], 100] (* A226130 *)
Take[Numerator[f], 100]   (* A226131 *)
p1 = Flatten[Table[Position[f, n], {n, 1, z}]] (* A226136 *)
p2 = Flatten[Table[Position[f, -n], {n, 0, z}]];
Union[p1, p2]  (* A226137 *)  (* Peter J. C. Moses, May 26 2013 *)

Python

from fractions import Fraction
from itertools import count, islice
def agen():
    rats = [Fraction(1, 1)]
    seen = {Fraction(1, 1)}
    for n in count(1):
        yield from [r.denominator for r in rats]
        newrats = []
        for r in rats:
            f = 1+r
            if f not in seen:
                newrats.append(1+r)
                seen.add(f)
            if r != 0:
                g = -1/r
                if g not in seen:
                    newrats.append(-1/r)
                    seen.add(g)
        rats = newrats
print(list(islice(agen(), 84))) # Michael S. Branicky, Jan 17 2022