The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 (list; graph; refs; listen; history; text; internal format)
 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 Table of n, a(n) for n=1..22. 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 Cf. A010060. Sequence in context: A221949 A262803 A026622 * A360785 A198896 A026688 Adjacent sequences: A297615 A297616 A297617 * A297619 A297620 A297621 KEYWORD nonn,more AUTHOR Jeffrey Shallit, Jan 01 2018 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 10 17:56 EDT 2023. Contains 363206 sequences. (Running on oeis4.)