k-automatic sequences
Jeffrey Shallit
elvis at graceland.uwaterloo.ca
Fri Jun 29 12:57:31 CEST 2001
Several people wrote to me asking about k-automatic sequences.
There are many equivalent definitions, but for people interested in
sequences the following definition is probably easiest: a sequence
(a(n)) is k-automatic if the set of distinct subsequences of the
form (a(k^i n + c))_{n >= 0}, where i >= 0 and 0 <= c < k^i, is finite.
An example is the Thue-Morse sequence, which is defined by t(n) = 1 if
there are an odd number of 1's in the base-2 expansion of n, 0 otherwise.
It is easy to write a program which attempts to deduce if a sequence is
of this form, based on some large number of computed values. Sometimes
this leads to interesting conjectures.
Another larger class is the k-regular sequences, where we replace
"finite" by "generates a finitely-generated Z-module".
Allouche and I are almost done writing a book on k-automatic and k-regular
sequences.
Jeffrey Shallit
More information about the SeqFan
mailing list