login
A297618
a(n) is the length of longest subsequence common to both the n-th Thue-Morse 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
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.
EXAMPLE
For n = 3, a longest common subsequence between mu^3(0) = 01101001 and its bitwise complement 10010110 is 01010.
CROSSREFS
Cf. A010060.
Sequence in context: A221949 A262803 A026622 * A360785 A198896 A026688
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Jan 01 2018
STATUS
approved