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

Comments

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.

Links

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

Example

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.

Prog

(PARI) See Links section.

Crossrefs

Cf. A232559, A293248.

Sequence in context: A214494 A088445 A280696 * A020653 A094522 A233204

Adjacent sequences: A293244 A293245 A293246 * A293248 A293249 A293250

Keyword

nonn,frac

Author

Rémy Sigrist, Oct 03 2017

Status

approved