A323442 - OEIS

%I #20 Jul 04 2022 19:49:58

%S 2,2,2,2,6,8,16,26,44,88,160,318,620,1234,2434,4860,9664,19282,38450,

%T 76804,153362,306524,612576,1224770,2448594,4896428,9790988,19580486,

%U 39157180,78311372,156615316,313224766,626434456,1252857082,2505684038,5011344512

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

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

%H Rémy Sigrist, <a href="/A323442/b323442.txt">Table of n, a(n) for n = 1..40</a>

%H Rémy Sigrist, <a href="/A323442/a323442.txt">C program for A323442</a>

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

%o (C) See Links section.

%o (Python)

%o from itertools import product as prod

%o def c(w): # string w begins or ends with a square

%o     if any(w[:i] == w[i:2*i] for i in range(1, len(w)//2+1)): return True

%o     if any(w[-i:] == w[-2*i:-i] for i in range(1, len(w)//2+1)): return True

%o     return False

%o def a(n):

%o     return sum(2 for b in prod("01", repeat=n-1) if not c("0"+"".join(b)))

%o print([a(n) for n in range(1, 21)]) # _Michael S. Branicky_, Jul 04 2022

%Y Similar to, but not the same as, A323443.

%K nonn

%O 1,1

%A _Jeffrey Shallit_, Jan 15 2019

%E a(21)-a(36) from _Lars Blomberg_, Jan 17 2019