A101387 - OEIS

%I #26 Mar 10 2017 13:00:15

%S 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 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 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 Quet transform of A002260.

%C 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 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 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 In the example b is 1,2,4,3,6,8,5,9,11,13,7,12,15,... (A065562).

%C 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 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 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 A more formal description of the Quet transform is as follows.

%C 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 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 Lars Blomberg, <a href="/A101387/b101387.txt">Table of n, a(n) for n = 1..10000</a>

%H David Wasserman, <a href="/A100661/a100661.txt">Quet transform + PARI code</a> [Cached copy]

%o (PARI)

%o \\ PARI code to compute the Quet transform.  Put the first n terms of the sequence

%o \\ into a vector v; then Q(v) returns the transformed sequence.  The output is a

%o \\ vector, containing as many terms as can be computed from the given data.

%o 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 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 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 Q(v) = T(PInverse(TInverse(v)));

%o \\ _David Wasserman_, Jan 14 2005

%Y Cf. A002260, A100661.

%K easy,nonn

%O 1,3

%A _David Wasserman_, Jan 14 2005