cp's OEIS Frontend

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

%I A362368 #39 May 31 2023 04:26:22
%S A362368 0,0,2,0,4,0,18,4,56,12,156,80,568,424,1856,2080,6548,8524,22430,
%T A362368 33840,80672,132704,292428,510892,1079282,1955388,3990564,7453012,
%U A362368 14928434,28406028,56125298,108156096,212297776
%N A362368 Number of binary strings of length n which are losing configurations in the palindrome game.
%C A362368 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.
%e A362368 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.
%e A362368 For n = 4, the four losing positions are 0011, 0101, 1010, 1100.
%e A362368 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.
%o A362368 (Python)
%o A362368 from functools import lru_cache
%o A362368 from itertools import product
%o A362368 def ispal(s): return s == s[::-1]
%o A362368 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]))
%o A362368 @lru_cache(maxsize=None)
%o A362368 def L(s): return all(not L(t) for t in m(s))
%o A362368 def a(n): return 2*sum(1 for p in product("01", repeat=n-1) if L("0"+"".join(p))) if n else 0
%o A362368 print([a(n) for n in range(16)]) # _Michael S. Branicky_, May 23 2023
%K A362368 nonn,more
%O A362368 0,3
%A A362368 _Kishore Rajesh_, Apr 17 2023
%E A362368 a(21)-a(29) from _Michael S. Branicky_, May 23 2023
%E A362368 a(30)-a(31) from _Michael S. Branicky_, May 26 2023
%E A362368 a(32) from _Michael S. Branicky_, May 30 2023