A323443 Number of binary squares of length 2n that neither begin nor end with a shorter square.

2, 2, 2, 2, 2, 8, 14, 26, 42, 84, 154, 314, 610, 1220, 2400, 4836, 9590, 19220, 38326, 76684, 153110, 306294, 612082, 1224304, 2447620, 4895468, 9789002, 19578586, 39153160, 78307450, 156607388, 313216848, 659125988, 1491573926, 2990216920, 5536326412

Offset

1,1

Comments

A square is a word of the form XX, where X is a nonempty block.

Links

Rémy Sigrist, Table of n, a(n) for n = 1..39

Rémy Sigrist, C program for A323443

Example

For n = 7 the squares are (0100001)^2, (0100110)^2, (0110001)^2, (0110010)^2, (0111001)^2, (0111101)^2, (0111110)^2 and their complements.

Prog

(C) See Links section.
(Python)
from itertools import product as prod
def c(w): # string ww begins or ends with a shorter square
    ww = w+w
    if any(ww[:i] == ww[i:2*i] for i in range(1, len(w))): return True
    if any(ww[-i:] == ww[-2*i:-i] for i in range(1, len(w))): return True
    return False
def a(n):
    return sum(2 for b in prod("01", repeat=n-1) if not c("0"+"".join(b)))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Jul 04 2022

Crossrefs

Similar to, but not the same as, A323442.

Sequence in context: A278241 A010671 A339164 * A334511 A291944 A253633

Adjacent sequences: A323440 A323441 A323442 * A323444 A323445 A323446

Keyword

nonn

Author

Jeffrey Shallit, Jan 15 2019

Extensions

More terms from Rémy Sigrist, Jan 19 2019

Status

approved