1,3

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.

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).

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).

In the example b is 1,2,4,3,6,8,5,9,11,13,7,12,15,... (A065562).

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).

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).

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).

A more formal decription of the Quet transform is as follows.

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.

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.

Leroy Quet, Home Page (listed in lieu of email address)

David Wasserman, Quet Transform

Cf. A002260, A100661.

Sequence in context: A110977 A069230 A163961 this_sequence A117365 A116212 A079068

Adjacent sequences: A101384 A101385 A101386 this_sequence A101388 A101389 A101390

easy,nonn,less

David Wasserman (wasserma(AT)spawar.navy.mil), Jan 14 2005