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.

%I A293247 #14 Oct 05 2017 09:54:24
%S A293247 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,
%T A293247 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,
%U A293247 13,11,5,3,1,16,15,14,13,12,11,6,5,4,3,2,1
%N 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.
%C A293247 See A293248 for the corresponding denominators.
%C A293247 The sequence S is a "rational" variant of A232559.
%C A293247 If r appears in S, then 1/r appears in S.
%C A293247 S is a permutation of the positive rational numbers:
%C A293247 - let f be the function u/v -> (u+1)/v
%C A293247   and g be the function u/v -> u/(v+1),
%C A293247 - let h^k be the k-th iterate of h,
%C A293247 - let r = u/v be a rational number in reduced form,
%C A293247 - without loss of generality, we can assume that u > v,
%C A293247 - according to Dirichlet's theorem on arithmetic progressions, we can choose a prime number p = k*u - 1 > u (where k > 2),
%C A293247 - we also have k*u - 1 > k*v,
%C A293247 - f^(p-1)(1) = p,
%C A293247 - g^(k*v-1)(f^(p-1)(1)) = p / (k*v) (and gcd(p, k*v)=1),
%C A293247 - f(g^(k*v-1)(f^(p-1)(1))) = (p+1) / (k*v) = (k*u) / (k*v) = u/v = r, QED.
%H A293247 Rémy Sigrist, <a href="/A293247/b293247.txt">Table of n, a(n) for n = 1..10000</a>
%H A293247 Wikipedia, <a href="https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions">Dirichlet's theorem on arithmetic progressions</a>
%H A293247 Rémy Sigrist, <a href="/A293247/a293247.png">Colorized scatterplot of A293247 vs. A293248 for n=1..100000</a>
%H A293247 Rémy Sigrist, <a href="/A293247/a293247.gp.txt">PARI program for A293247</a>
%e A293247 S(1) = 1 by definition; so a(1) = 1.
%e A293247 (1+1)/1 = 2 has not yet occurred; so S(2) = 2 and a(2) = 2.
%e A293247 1/(1+1) = 1/2 has not yet occurred; so S(3) = 1/2 and a(3) = 1.
%e A293247 (2+1)/1 = 3 has not yet occurred; so S(4) = 3 and a(4) = 3.
%e A293247 2/(1+1) = 1 has already occurred.
%o A293247 (PARI) See Links section.
%Y A293247 Cf. A232559, A293248.
%K A293247 nonn,frac
%O A293247 1,2
%A A293247 _Rémy Sigrist_, Oct 03 2017