[seqfan] Kolakoski, Golomb, and transforms

[franktaw at netscape.net]

It occurred to me the other day that the Kolakoski sequence, A000002, 
is the first (index k = 2) of a sequence of sequences which approach 
the Golomb sequence A001462 as their limit.  In fact, Benoit Cloitre 
got there before me: see A079729 and A079730, which are k = 3 and k = 4.

In fact this can be generalized further.  Let us make some definitions:

Given sequences b(i) and c(i), i >= 1, with b(i) a sequence of 
non-negative integers, the cardinal transform of b(i) and c(i) is the 
sequence with b(1) copies of c(1), b(2) copies of c(2), etc.  If b is 
zero from some point on, the result will be a finite sequence; 
otherwise it will be infinite.

If b is a sequence for which b(i-1) != b(i) infinitely often, the 
run-length transform is the sequence of run lengths of b.  One way to 
define this is to take c to be the sequence, starting with 1, of all i 
such that b(i-1) != b(i); the run-length transform is then the first 
differences of c.

Similarly, the run-unique transform of b is the maximal subsequence of 
b with no consecutive equal values.  For b and c as above, we have a(i) 
= b(c(i)).

These are obviously inverse transforms in the following sense: if a is 
a sequence for which the run-length and run-unique transforms are 
defined, then cardinal(run-count(a), run-unique(a)) is again the 
sequence a.  Conversely, if b is a sequence of positive integers, and c 
has no consecutive equal elements, then run-count(cardinal(b,c)) = b 
and run-unique(cardinal(b,c)) = c.

Now we can define the Kolakoski-Golomb transform.  This applies to a 
sequence b of positive integers.  We want Kolakoski-Golomb(b) to be the 
unique sequence a such that cardinal(a,b) = a.

When the sequence b has no consecutive values equal, a = 
Kolakoski-Golomb(b) will have run-count(a) = a, and all such sequences 
can be described in this way (since run-unique(a) = b under these 
conditions).

(In fact, the transform can be extended to sequences b which contain 
zeros, provided that for any k, sum_{i=1}^k b(i) >= k.)

The Kolakoski sequence is the Kolakoski-Golumb transform applied to the 
sequence 1,2,1,2,1,2,... (A000034).  The Golomb sequence is the 
Kolakoski-Golumb transform of the natural numbers A000027.  The 
aforementioned A079729 is the Kolakoski-Golumb transform of 
1,2,3,1,2,3,... (A010882) and A079730 is the transform of A010883.

Also in the database: A064353 is the Kolakoski-Golumb transform of 
1,3,1,3,1,3,... (A010684), and A078880 is the transform of 
2,1,2,1,2,1,....

There are a number of sequences in the database which can be easily 
described using the cardinal transform, usually with the natural 
numbers or the non-negative integers (A001477) as the second parameter. 
  Some of these are: A000194, A000196, A002024, A003056, A036042, 
A061017, A113473.

The cardinal transform can also be used to describe subsequences: if b 
is the characteristic function for a set S, cardinal(b,c) is the 
elements of c indexed by members of S.

Franklin T. Adams-Watters