login
A323443
Number of binary squares of length 2n that neither begin nor end with a shorter square.
2
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
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
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Jan 15 2019
EXTENSIONS
More terms from Rémy Sigrist, Jan 19 2019
STATUS
approved