login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A340314 Number of different possible profiles of palindromic length for prefixes of sequences of length n, over an arbitrary (unbounded) alphabet. 1
1, 2, 5, 11, 27, 63, 155, 376, 922, 2245, 5506 (list; graph; refs; listen; history; text; internal format)
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, over all length-n sequences over an arbitrary (unbounded) alphabet.
LINKS
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
alphabet = [chr(c) for c in range(ord('0'), ord('0')+n)]
return len(set(plp('0'+"".join(u)) for u in product(alphabet, repeat=n-1)))
print([a(n) for n in range(1, 8)]) # Michael S. Branicky, Jan 04 2021
CROSSREFS
Cf. A340311.
Sequence in context: A266545 A095975 A006652 * A238825 A073225 A027087
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Jan 04 2021
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 08:13 EDT 2024. Contains 371265 sequences. (Running on oeis4.)