A338761 Subword complexity of a certain infinite word.

1, 2, 4, 8, 13, 22, 37, 57, 85, 120, 165, 219, 285, 362, 453, 557, 677, 812, 965, 1135, 1325, 1534, 1765, 2017, 2293, 2592, 2917, 3267, 3645, 4050, 4485, 4949, 5445, 5972, 6533, 7127, 7757, 8422, 9125, 9865, 10645, 11464, 12325, 13227, 14173, 15162, 16197

Offset

0,2

Comments

The infinite word is (ab)(abb.aab)(abbb.aabb.aaab)(abbbb.aabbb.aaabb.aaaab)... . Subword complexity is the number of distinct length-n blocks appearing in the sequence.

Links

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

L. Schaeffer and K. Wu, Two Infinite Words with Cubic Subword Complexity, J. Integer Sequences 23 (2020), Paper 20.10.8.

Formula

Equal to 2^n for n <= 3, and n^3/6-2n/3+(19+(-1)^n)/4 for n >= 4.

Example

For n=4 the only subwords omitted are {abaa, baba, bbab}.

Crossrefs

Cf. A338760.

Sequence in context: A244985 A164413 A164441 * A023600 A164437 A164428

Adjacent sequences: A338758 A338759 A338760 * A338762 A338763 A338764

Keyword

nonn

Author

Jeffrey Shallit, Nov 07 2020

Status

approved