Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the 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