A362368 Number of binary strings of length n which are losing configurations in the palindrome game.

0, 0, 2, 0, 4, 0, 18, 4, 56, 12, 156, 80, 568, 424, 1856, 2080, 6548, 8524, 22430, 33840, 80672, 132704, 292428, 510892, 1079282, 1955388, 3990564, 7453012, 14928434, 28406028, 56125298, 108156096, 212297776

Offset

0,3

Comments

The palindrome game is a game where players take turns removing a nonempty palindrome from a binary string. The player who crosses off the last palindrome wins. The nonempty palindrome can be removed from anywhere in the current string.

Links

Table of n, a(n) for n=0..32.

Example

For n = 2, 10 and 01 are losing strings since the first player has to cross out either the first or second character, leaving the second player with a string of length 1, which is always a palindrome. 00 and 11 are not losing strings since the first player can cross out the entire string and win.
For n = 4, the four losing positions are 0011, 0101, 1010, 1100.
For n = 5, 00101 is winning since the first player may put the second in a losing position by removing 010 from the center or by removing either of the first two 0's.

Prog

(Python)
from functools import lru_cache
from itertools import product
def ispal(s): return s == s[::-1]
def m(s): yield from (s[:i]+s[j:] for i in range(len(s)) for j in range(i+1, len(s)+1) if ispal(s[i:j]))
@lru_cache(maxsize=None)
def L(s): return all(not L(t) for t in m(s))
def a(n): return 2*sum(1 for p in product("01", repeat=n-1) if L("0"+"".join(p))) if n else 0
print([a(n) for n in range(16)]) # Michael S. Branicky, May 23 2023

Crossrefs

Sequence in context: A022896 A100225 A007420 * A019219 A019139 A285774

Adjacent sequences: A362365 A362366 A362367 * A362369 A362370 A362371

Keyword

nonn,more

Author

Kishore Rajesh, Apr 17 2023

Extensions

a(21)-a(29) from Michael S. Branicky, May 23 2023

a(30)-a(31) from Michael S. Branicky, May 26 2023

a(32) from Michael S. Branicky, May 30 2023

Status

approved