

A297618


a(n) is the length of longest subsequence common to both the nth ThueMorse word and its bitwise complement.


1



1, 2, 5, 12, 26, 54, 110, 226, 462, 942, 1908, 3850, 7752, 15614, 31416, 63150, 126964, 254870, 511086, 1024796, 2053960, 4116976
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The nth ThueMorse word is the nth iterate of the morphism mu(0) = 01, mu(1) = 10. Thus mu^1(0) = 01, mu^2(0) = 0110, mu^3(0) = 01101001, etc.
Here by "subsequence" we mean "not necessarily contiguous subsequence".
Recently, Joakim Blikstad has proved that a(n) = 2^n(1o(1)).  Jeffrey Shallit, Oct 26 2018


LINKS



EXAMPLE

For n = 3, a longest common subsequence between mu^3(0) = 01101001 and its bitwise complement 10010110 is 01010.


CROSSREFS



KEYWORD

nonn,more


AUTHOR



STATUS

approved



