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

Author

Rémy Sigrist, Oct 03 2017

Keywords

• nonn
• frac

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.

Examples

			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.
		

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

Crossrefs

Cf. A232559, A293248.

Programs

PARI

See Links section.