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

Author

Jeffrey Shallit, Dec 31 2017

Keywords

• nonn

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.

Examples

			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.

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