[seqfan] Sequences that are fixed points of mappings
njasloane at gmail.com
Sun Oct 2 17:26:40 CEST 2016
Dear Seq Fans, There are many sequences that have definitions like:
A276397 Trajectory of 0 under the morphism 0 -> 001, 1 -> 0010.
The Fibonacci word (A003849), the Thue-Morse sequence (A010060), etc are
There is an entry in the Index to the OEIS for such sequences,
see https://oeis.org/wiki/Index_to_OEIS:_Section_Fi under "fixed points of
I just updated the Index, so now there are about 120 index entries for such
sequences, and I also added links for all those sequences to the index
However, I probably missed a lot, because many of these sequences use
different wording to say thing like "Image of x under repeated application
of the map replace 1 by ..., 2 by ..., 3 by ..."
By the way, this is all about sequences over a finite alphabet. We are
talking about operations on strings, NOT arithmetical operations like the
3x+1 map or "reverse and add". The subject here is "Combinatorics on
Why I am writing this is to invite people to add more existing OEIS
sequences of this class to the Index. Also to say that almost all these
sequences (except the most famous ones) need b-files.
Also, I don't have a good test for such sequences. Given the beginning of
a sequence over a finite alphabet, is it a trajectory of some morphism?
There may be many sequences
of this type in the OEIS which are not yet identified as such. Superseeker
does not include
a test for them, and I wish it did.
The great book "Automatic Sequences" by sequence fans Allouche and Shallitt
has a NASC for an infinite sequence to be of this type in Theorem 7.3.1
page 216, but I'm not sure how to use that in a program that humans or
Superseeker could use.
More information about the SeqFan