[seqfan] Kolakoski, Golomb, and transforms
franktaw at netscape.net
franktaw at netscape.net
Fri Mar 13 10:51:32 CET 2009
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
More information about the SeqFan
mailing list