A350774 Abelian complexity of the Rudin-Shapiro sequence (A020985).

2, 3, 4, 5, 4, 5, 6, 7, 6, 7, 8, 9, 8, 9, 10, 11, 10, 9, 8, 9, 8, 9, 10, 11, 10, 11, 12, 13, 12, 13, 14, 15, 14, 13, 12, 13, 12, 13, 14, 15, 14, 15, 16, 17, 16, 17, 18, 19, 18, 17, 16, 17, 16, 17, 18, 19, 18, 19, 20, 21, 20, 21, 22, 23, 22, 21, 20, 21, 20, 19

Offset

1,1

Comments

a(n) = the number of contiguous length-n blocks in A020985, where two blocks that differ only the order of their letters are considered the same.

Links

Table of n, a(n) for n=1..70.

X. Lü, J. Chen, Z. Wen, and W. Wu, On the abelian complexity of the Rudin-Shapiro sequence, J. Math. Anal. Appl. 451 (2017), 822-838.

Formula

a(4n+1) = 2a(n)

a(4n+3) = -2a(n) + 2a(4n+2)

a(8n) = -2a(n) + 2a(2n) + a(4n)

a(8n+2) = a(2n) + a(2n+1)

a(16n+4) = 4a(n) - a(2n+1) + a(8n+4)

a(16n+6) = 2a(n) + a(4n+2)

a(16n+12) = -4a(n) - 2a(2n+1) + 4a(4n+2) + a(8n+4)

a(16n+14) = -4a(n) - 2a(2n+1) + 4a(4n+2) + a(8n+4)

Example

For n=5 there are 24 distinct subwords, but only 4 up to abelian equivalence.

Crossrefs

Cf. A020985.

Sequence in context: A302981 A205785 A303235 * A282062 A318126 A326167

Adjacent sequences: A350771 A350772 A350773 * A350775 A350776 A350777

Keyword

nonn

Author

Jeffrey Shallit, Jan 15 2022

Status

approved