|
%I #13 Feb 05 2021 00:48:57
%S 2,4,4,10,16,28,44,90,156,270,488,886,1620,2986,5460,10120,18890,
%T 35284,66290,124964,236040,447460,850492,1620016,3092652,5915898,
%U 11336182,21760238,41836338,80549326,155296862,299788294,579396418,1121031734,2171251698
%N Number of length-n binary words whose longest repeated suffix equals the longest repeated prefix.
%C The longest repeated suffix of a word x is the longest suffix (possibly empty) that occurs at least twice as a contiguous block inside x, and analogously for the prefix.
%H Michael S. Branicky, <a href="/A327544/a327544.py.txt">Python program.</a>
%e For n = 5 these binary words are 00000, 00100, 00110, 01001, 01010, 01100, 01101, 01110 and their reversals.
%o (Python) # see link for faster version
%o from itertools import product
%o def lrp(s): # longest repeated prefix (overlaps allowed)
%o for i in range(len(s)-1, 0, -1):
%o if s.find(s[:i], 1) >= 0: return s[:i]
%o return ""
%o def a(n):
%o if n == 1: return 2
%o c = 0
%o for p in product("01", repeat=n-1):
%o b = "1" + "".join(p)
%o if lrp(b) == lrp(b[::-1])[::-1]: c += 1
%o return 2*c
%o print([a(n) for n in range(1, 17)]) # _Michael S. Branicky_, Feb 05 2021
%K nonn
%O 1,1
%A _Jeffrey Shallit_, Sep 16 2019
%E a(29) and beyond from _Michael S. Branicky_, Feb 05 2021
|
