OFFSET
1,2
COMMENTS
The n-th Thue-Morse word is the n-th 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(1-o(1)). - Jeffrey Shallit, Oct 26 2018
LINKS
J. Berstel, Combinatorics on Words Examples and Problems, talk in Turku, Finland, May 24 2006.
Joakim Blikstad, On the longest common subsequence of Thue-Morse words, arXiv:1904.00248 [cs.DM], 2019.
Wikipedia, Longest common subsequence problem
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
Jeffrey Shallit, Jan 01 2018
STATUS
approved