A non-periodic sequence of s and
s, with no 3 consecutive identical blocks of any length.
Ways of constructing it:
1. For each nonnegative integer , let
if the number of
‘s in the binary representation of
is even, and
if this number is odd. (Conway calls these evil and odious numbers, respectively)
2. At each step, append a copy of the sequence so far, with s and
s interchanged.
i.e. Start with . Append
to that.
.
Append to that
.
Append to that
.
Append to that
. etc.
3. Start with . Apply
and
.
If is
in binary notation, then
, with the same number of binary
s as
, and
, containing one more
. So:
i.e. the sequence is determined by its odd-numbered terms, and each of those is different to the previous (even) term.
Interpreted as a binary fraction, , the Morse-Thue constant, it’s intimately related to period-doubling bifurcation and the Mandelbrot set.
The Tarry-Escott problem
Can the set be partitioned into two disjoint subsets
and
such that
The Thue-Morse sequence determines such a partitioning.
Let be the set of all
with
,
and be the set of
with
.
e.g. Take .
The first 16 terms of the sequence are , so
, and
.
And sure enough…
,
,
,
.
This works for any polynomial of degree .
If if a polynomial of degree not exceeding
, then
Further reading
Savchev, Andreescu – Mathematical Miniatures (2002)
Manfred Schroeder – Fractals, Chaos, Power Laws