cp's OEIS Frontend

A101387 Quet transform of A002260.

%I A101387 #26 Mar 10 2017 13:00:15
%S A101387 1,1,2,1,3,1,5,1,1,7,1,2,1,9,1,3,1,12,1,1,4,1,15,1,2,1,5,1,18,1,3,1,7,
%T A101387 1,1,21,1,4,1,9,1,2,1,24,1,5,1,11,1,3,1,28,1,1,6,1,13,1,4,1,32,1,2,1,
%U A101387 7,1,15,1,5,1,36,1,3,1,9,1,1,17,1,6,1,40,1,4,1,11,1,2,1,19,1,7,1,44,1,5,1
%N A101387 Quet transform of A002260.
%C A101387 The Quet transform converts any sequence of positive integers containing an infinite number of 1's into another sequence of positive integers containing an infinite number of 1's.
%C A101387 Start with a sequence, {a(k)}, of only positive integers and an infinite number of 1's. Example: 1,1,2,1,2,3,1,2,3,4,1,... (A002260).
%C A101387 Form the sequence {b(k)} (which is a permutation of the positive integers), given by b(k) = the a(k)th smallest positive integer not yet in the sequence b, with b(1)=a(1).
%C A101387 In the example b is 1,2,4,3,6,8,5,9,11,13,7,12,15,... (A065562).
%C A101387 Let {c(k)} be the inverse of {b(k)}. In the example c = 1,2,4,3,7,5,11,6,8,16,9,12... (A065579).
%C A101387 Form the final sequence {d(k)}, where each d(k) is such that c(k) = the d(k)th smallest positive integer not yet in the sequence c, with d(1)=c(1).
%C A101387 In the example d is 1,1,2,1,3,1,5,1,1,7,1,2,1,9,1,3,1,12,1,1,4,1,15,... (the current sequence).
%C A101387 A more formal description of the Quet transform is as follows.
%C A101387 Let N denote the positive integers. For any permutation p: N -> N, let T(p): N -> N be given by T(p)(n) = # of elements in {m in N | m >= n AND p(m) <= p(n)}. Observe that T is a bijection from the set of permutations N -> N onto the set of sequences N -> N that contain infinitely many 1's.
%C A101387 Now suppose f: N -> N contains infinitely many 1's; then its Quet transform Q(f): N -> N is T^(-1)[(T(f))^(-1)], which also contains infinitely many 1's. Q is self-inverse; f and Q(f) correspond via T to a permutation and its inverse.
%H A101387 Lars Blomberg, <a href="/A101387/b101387.txt">Table of n, a(n) for n = 1..10000</a>
%H A101387 David Wasserman, <a href="/A100661/a100661.txt">Quet transform + PARI code</a> [Cached copy]
%o A101387 (PARI)
%o A101387 \\ PARI code to compute the Quet transform.  Put the first n terms of the sequence
%o A101387 \\ into a vector v; then Q(v) returns the transformed sequence.  The output is a
%o A101387 \\ vector, containing as many terms as can be computed from the given data.
%o A101387 TInverse(v) = local(l, w, used, start, x); l = length(v); w = vector(l); used = vector(l); start = 1; for (i = 1, l, while (start <= l && used[start], start++); x = start; for (j = 2, v[i], x++; while (x <= l && used[x], x++)); if (x > l, return (vector(i - 1, k, w[k])), w[i] = x; used[x] = 1)); w;
%o A101387 PInverse(v) = local(l, w); l = length(v); w = vector(l); for (i = 1, l, if (v[i] <= l, w[v[i]] = i)); w;
%o A101387 T(v) = local(l, w, c); l = length(v); w = vector(l); for (n = 1, l, if (v[n], c = 0; for (m = 1, n - 1, if (v[m] < v[n], c++)); w[n] = v[n] - c, return (vector(n - 1, i, w[i])))); w;
%o A101387 Q(v) = T(PInverse(TInverse(v)));
%o A101387 \\ _David Wasserman_, Jan 14 2005
%Y A101387 Cf. A002260, A100661.
%K A101387 easy,nonn
%O A101387 1,3
%A A101387 _David Wasserman_, Jan 14 2005