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

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.

Sequence in context: A233349 A233556 A087148 * A334821 A275489 A153817

Adjacent sequences: A297528 A297529 A297530 * A297532 A297533 A297534

Keyword

nonn

Author

Jeffrey Shallit, Dec 31 2017

Status

approved