|
%I #21 Jul 04 2022 19:50:15
%S 2,2,2,2,2,8,14,26,42,84,154,314,610,1220,2400,4836,9590,19220,38326,
%T 76684,153110,306294,612082,1224304,2447620,4895468,9789002,19578586,
%U 39153160,78307450,156607388,313216848,659125988,1491573926,2990216920,5536326412
%N Number of binary squares of length 2n that neither begin nor end with a shorter square.
%C A square is a word of the form XX, where X is a nonempty block.
%H Rémy Sigrist, <a href="/A323443/b323443.txt">Table of n, a(n) for n = 1..39</a>
%H Rémy Sigrist, <a href="/A323443/a323443.txt">C program for A323443</a>
%e For n = 7 the squares are (0100001)^2, (0100110)^2, (0110001)^2, (0110010)^2, (0111001)^2, (0111101)^2, (0111110)^2 and their complements.
%o (C) See Links section.
%o (Python)
%o from itertools import product as prod
%o def c(w): # string ww begins or ends with a shorter square
%o ww = w+w
%o if any(ww[:i] == ww[i:2*i] for i in range(1, len(w))): return True
%o if any(ww[-i:] == ww[-2*i:-i] for i in range(1, len(w))): 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, A323442.
%K nonn
%O 1,1
%A _Jeffrey Shallit_, Jan 15 2019
%E More terms from _Rémy Sigrist_, Jan 19 2019
|
