# shortest string containing all binary palindrome of length n as substring

I am trying to compute the shortest binary string that contains all binary palindrome of length n as substring. For example, for n=3, 00010111 is such a shortest string. However, brutal force performs really bad even for n=6, n=7 etc. Is there any optimization like branch and bound I can do here. My current optimization is following:

1. Use common super sequence algorithm to get an upper bound of the target string

2. palindrome of all 0 and all 1 is contained there hence we can place the first n position as 0 and last n position as 1

3. a continuous block of more than n-2 "1"s or "0"s is clearly not in shortest target string, hence this kind of situation should be avoided.

However, the above optimization is not enough, the program cannot even terminate in reasonable time for n=7.

Hence I am asking if anyone can get some further optimization

• Jeffrey Shallit could work out the case $n=6$. See A330022. May 22, 2020 at 10:29
• It's not clear to me why (2) holds (i.e., why you can be sure that there is a minimal solution beginning with $n$ 0s and ending with $n$ 1s). Also (3) seems to contradict (2). May 22, 2020 at 23:40
• Have you tried using a SAT solver?
– D.W.
May 23, 2020 at 3:34