|
|
A318916
|
|
Minimum length of longest palindromic subsequence, where the minimum is taken over all binary circular words of length n.
|
|
0
|
|
|
1, 1, 3, 3, 5, 5, 6, 7, 7, 8, 9, 9, 11, 11, 12, 13, 13, 14, 15, 15, 17, 17, 18, 19, 19, 20, 21, 21, 22, 23, 23, 24
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Here "subsequence" means "scattered subsequence" (not necessarily contiguous). A circular word "wraps around".
Slide 10 of Andrew Ryzhikov's talk contains the conjecture that a(n) >= 3n/4, but this conjecture fails for n = 2 and n = 62 (at least). The length-62 counterexample 11111111000000000001010001110110000011010011111001000111010111, where the longest palindromic subsequence is of length 45, was found by Antonio Molina Lovett.
|
|
LINKS
|
|
|
EXAMPLE
|
Consider the circular word 0001011. A rotation of this circular word gives 0101100, and deleting the first 1 gives the subsequence 001100, which is a palindrome of length 6. This shows that a(7) >= 6.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Terms a(19)-a(32) computed by Antonio Molina Lovett
|
|
STATUS
|
approved
|
|
|
|