# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a327544
Showing 1-1 of 1

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

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE