Self-Generating Sets, Missing Blocks, and Substitutions

We generalize the result of Allouche, Shallit, and Skordev regarding the Kimberling sequence, defined by:

  1. $1$ belongs to $S$;
  2. if the integer $x$ belongs to $S$, then $2x$ and $4x-1$ are also in $S$;
  3. nothing else is in $S$. Thus:

$$S = 1\ 2\ 3\ 4\ 6\ 7\ 8\ 11\ 12\ 14\ 15\ 16\ldots$$

The set $T=S-1$, with its first term removed, is both the set of integers whose binary expansions contain no 00 block and the fixed point of the Fibonacci morphism $0\rightarrow01$, $1\rightarrow0$. We expand this result to the natural generalization of the Fibonacci morphism, of the form $0\rightarrow0^n1$, $1\rightarrow0$

David Failing
David Failing

Lead Data Scientist and Consultant

Mathematics Instructor