A229614 -id:A229614 - cp's OEIS frontend

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

1, 2, 4, 8, 12, 20, 26, 38, 42, 52, 56, 56, 48, 42, 32, 22, 10, 4, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Nathaniel Johnston, Oct 10 2013

Entringer et al. showed that a(n) = 0 for all n >= 19.

			a(4) = 12 because there are 16 binary strings of length 4, but 4 of these strings (namely 0000, 0101, 1010, and 1111) repeat a substring of length 2. Thus a(4) = 16 - 4 = 12.
a(18) = 2 because there are 2 strings of length 18 not containing any "squares" of length greater than 1: 010011000111001101 and 101100111000110010.

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

Cf. A022087, A229614, A230177.

a[n_] := a[n] = Select[PadLeft[#, n]& /@ IntegerDigits[Range[0, 2^n-1], 2], {} == SequencePosition[#, {b__, b__} /; Length[{b}]>1, 1]&] // Length;
Table[Print[n, " ", a[n]]; a[n], {n, 0, 20}] (* Jean-François Alcover, Nov 10 2021 *)

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

Original entry on oeis.org

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

Nathaniel Johnston, Oct 11 2013

nonn

			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.

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

Cf. A229614, A230127, A230216.

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

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 56, 104, 192, 352, 648, 1192, 2192, 4032, 7416, 13640, 25088, 46144, 84872, 156104, 287120, 528096, 971320, 1786536, 3285952, 6043808, 11116296, 20446056, 37606160, 69168512, 127220728, 233995400, 430384640, 791600768, 1455980808

Offset: 0

Nathaniel Johnston, Oct 11 2013

			For n = 6 there are 8 strings omitted, namely 000000, 001001, ..., 111111, so a(6) = 64-8 = 56.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,1,1).

Cf. A000073, A022087, A229614, A230127, A230177.

Vec((1 + x + x^2 + x^3 + 2*x^4 + 4*x^5) / (1 - x - x^2 - x^3) + O(x^40)) \\ Colin Barker, Aug 09 2019

a(n) = 8*A000073(n) for n >= 3.
From Colin Barker, Aug 09 2019: (Start)
G.f.: (1 + x + x^2 + x^3 + 2*x^4 + 4*x^5) / (1 - x - x^2 - x^3).
a(n) = a(n-1) + a(n-2) + a(n-3) for n>5.
(End)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Examples

Links

Crossrefs

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula