[seqfan] Sequences that are fixed points of mappings

Neil Sloane 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
famous examples.

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
mappings"

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

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
Words".

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 mailing list