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

Author

Kishore Rajesh, Apr 17 2023

Keywords

• nonn
• more

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.

Examples

			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.
		

Programs

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

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