|
|
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
|
|
|
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
|
|
|
|