login
A308465
Number of prefix normal palindromes of length n.
0
2, 2, 3, 3, 5, 4, 8, 7, 12, 11, 21, 18, 36, 31, 57, 55, 104, 91, 182, 166, 308, 292, 562, 512, 1009, 928, 1755, 1697, 3247, 2972, 5906, 5555, 10506, 10099, 19542, 18280, 36002, 33895, 64958, 63045, 121887, 114032, 226065, 215377, 412749, 399334, 778196, 735941
OFFSET
1,1
LINKS
Pamela Fleischmann, On Special k-Spectra, k-Locality, and Collapsing Prefix Normal Words, Ph.D. Dissertation, Kiel University (Germany, 2021).
Pamela Fleischmann, Mitja Kulczynski, and Dirk Nowotka, On Collapsing Prefix Normal Words, arXiv:1905.11847 [cs.FL], 2019.
Pamela Fleischmann, Mitja Kulczynski, Dirk Nowotka, and Danny Bøgsted Poulsen, On Collapsing Prefix Normal Words, Language and Automata Theory and Applications (LATA 2020) LNCS Vol. 12038, Springer, Cham, 412-424.
PROG
(Python)
from itertools import product
def is_prefix_normal(w):
for k in range(1, len(w)+1):
weight0 = w[:k].count("1")
for j in range(1, len(w)-k+1):
weightj = w[j:j+k].count("1")
if weightj > weight0: return False
return True
def bin_pals(digits):
midrange = [[""], ["0", "1"]]
for p in product("01", repeat=digits//2):
left = "".join(p)
for middle in midrange[digits%2]:
yield left+middle+left[::-1]
def a(n):
return sum(is_prefix_normal(w) for w in bin_pals(n))
print([a(n) for n in range(1, 31)]) # Michael S. Branicky, Dec 19 2020
CROSSREFS
Cf. A016116 (numbers of binary palindromes), A194850 (number of prefix normal words)
Sequence in context: A114328 A097366 A139807 * A276119 A167755 A259788
KEYWORD
nonn
AUTHOR
Michel Marcus, May 29 2019
EXTENSIONS
a(31)-a(48) from Michael S. Branicky, Dec 19 2020
STATUS
approved