A230177 Number of binary strings of length n avoiding "squares" (that is, repeated blocks of the form xx) with |x| > 3.

1, 2, 4, 8, 16, 32, 64, 128, 240, 464, 866, 1642, 3048, 5720, 10642, 19868, 36894, 68722, 127630, 237324, 440594, 818584, 1519802, 2822630, 5240262, 9730478, 18065252, 33542006, 62272196, 115616582, 214646190, 398507348, 739840164, 1373551484, 2550032248

Offset: 0

Author

Nathaniel Johnston, Oct 11 2013

Keywords

• nonn

Examples

			a(8) = 256 - 16 = 240 because there are 256 binary strings of length 8, 16 of which contain a repeated block of length 4: 00000000, 00010001, 00100010, ..., 11111111.
		

Links

• R. C. Entringer, D. E. Jackson and J. A. Schatz, On nonrepetitive sequences, J. Combin. Theory Ser. A. 16 (1974), 159-164.
• Nathaniel Johnston, C code for computing this sequence

Crossrefs

Cf. A229614, A230127, A230216.