A297531 - OEIS

A297531

Subword complexity (number of distinct blocks) of length n occurring in the "twisted" Thue-Morse sequence.

1, 2, 4, 6, 10, 13, 17, 21, 24, 26, 30, 34, 38, 42, 45, 48, 50, 52, 56, 60, 64, 68, 72, 76, 80, 84, 87, 90, 93, 96, 98, 100, 102, 104, 108, 112, 116, 120, 124, 128, 132, 136, 140, 144, 148, 152, 156, 160, 164, 168, 171, 174, 177, 180, 183, 186, 189, 192, 194, 196, 198, 200, 202, 204, 206, 208, 212, 216, 220, 224, 228, 232, 236, 240

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

The "twisted" Thue-Morse sequence 00100110100... is the one given in A059448, but prefixed with 0. It is the image, under the map sending 0, 2 -> 0 and 1 -> 1 of the fixed point, starting with 0, of the morphism 0 -> 02, 1 -> 21, 2 -> 12.

This sequence has the maximum possible subword complexity over all binary overlap-free words.

LINKS

Table of n, a(n) for n=0..73.

FORMULA

For n >= 4 we have a(n+1) =

4n - 3*2^{i-2} for 2^i <= n <= 3*2^{i-1};

3n + 3*2^{i-2} for 3*2^{i-1} <= n <= 7*2^{i-2};

2n + 5*2^{i-1} for 7*2^{i-2} <= n <= 2^{i+1}.

EXAMPLE

For n=3 we have a(3) = 6, corresponding to the blocks 001, 010, 100, 011, 110, 101.

CROSSREFS

Cf. A005942, which enumerates the same thing for the ordinary Thue-Morse sequence A010060.