A340311 Number of different possible profiles of palindromic length for prefixes of binary sequences of length n.

1, 2, 4, 6, 10, 17, 32, 61, 117, 218, 424, 795, 1533, 2922, 5590, 10720, 20592, 39564, 76082, 146591, 282059, 544377, 1049753, 2026788, 3912391, 7559884

Offset

1,2

Comments

The palindromic length of a sequence is the minimum number of terms needed to write it as a concatenation of palindromes. For example, 011010 has palindromic length 3, as it can be written as (0110)(1)(0) or (0)(11)(010), but there is no way to write it as the concatenation of two palindromes.

The profile is the list of palindromic lengths of all prefixes. For 011010 it is (1,2,2,1,2,3). This sequence counts the distinct profiles.

Links

Table of n, a(n) for n=1..26.

Anna E. Frid, Prefix palindromic length of the Thue-Morse word, arXiv:1906.09392 [cs.DM], 2019.

Prog

(Python)
from functools import lru_cache
from itertools import product
def ispal(w): return w == w[::-1]
@lru_cache(maxsize=None)
def pal_len(w):
  if len(w) <= 1: return len(w)
  return min(1+pal_len(w[i:]) for i in range(len(w), 0, -1) if ispal(w[:i]))
def plp(w): # palindrome length profile
  return tuple(pal_len(w[:i]) for i in range(1, len(w) + 1))
def a(n):   # only search strings starting with 0 by symmetry
  return len(set(plp("0"+"".join(u)) for u in product("01", repeat=n-1)))
print([a(n) for n in range(1, 18)])  # Michael S. Branicky, Jan 04 2021

Crossrefs

Cf. A340314.

Sequence in context: A144023 A018164 A321403 * A025052 A142584 A098197

Adjacent sequences: A340308 A340309 A340310 * A340312 A340313 A340314

Keyword

nonn,more

Author

Jeffrey Shallit, Jan 04 2021

Extensions

a(21)-a(26) from Michael S. Branicky, Jan 04 2021

Status

approved