A323442 Number of length-n binary strings that neither begin nor end with a square.

2, 2, 2, 2, 6, 8, 16, 26, 44, 88, 160, 318, 620, 1234, 2434, 4860, 9664, 19282, 38450, 76804, 153362, 306524, 612576, 1224770, 2448594, 4896428, 9790988, 19580486, 39157180, 78311372, 156615316, 313224766, 626434456, 1252857082, 2505684038, 5011344512

Offset

1,1

Comments

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

Links

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

Rémy Sigrist, C program for A323442

Example

For n = 6 the 8 examples are {010001,011001,011101,011110} and their complements.

Prog

(C) See Links section.
(Python)
from itertools import product as prod
def c(w): # string w begins or ends with a square
    if any(w[:i] == w[i:2*i] for i in range(1, len(w)//2+1)): return True
    if any(w[-i:] == w[-2*i:-i] for i in range(1, len(w)//2+1)): 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, A323443.

Sequence in context: A376947 A230096 A116564 * A078014 A063867 A024723

Adjacent sequences: A323439 A323440 A323441 * A323443 A323444 A323445

Keyword

nonn

Author

Jeffrey Shallit, Jan 15 2019

Extensions

a(21)-a(36) from Lars Blomberg, Jan 17 2019

Status

approved