A308465 - OEIS

%I #20 Jul 02 2021 16:52:58

%S 2,2,3,3,5,4,8,7,12,11,21,18,36,31,57,55,104,91,182,166,308,292,562,

%T 512,1009,928,1755,1697,3247,2972,5906,5555,10506,10099,19542,18280,

%U 36002,33895,64958,63045,121887,114032,226065,215377,412749,399334,778196,735941

%N Number of prefix normal palindromes of length n.

%H Pamela Fleischmann, <a href="https://macau.uni-kiel.de/servlets/MCRFileNodeServlet/macau_derivate_00002273/diss.pdf">On Special k-Spectra, k-Locality, and Collapsing Prefix Normal Words</a>, Ph.D. Dissertation, Kiel University (Germany, 2021).

%H Pamela Fleischmann, Mitja Kulczynski, and Dirk Nowotka, <a href="https://arxiv.org/abs/1905.11847">On Collapsing Prefix Normal Words</a>, arXiv:1905.11847 [cs.FL], 2019.

%H Pamela Fleischmann, Mitja Kulczynski, Dirk Nowotka, and Danny Bøgsted Poulsen, <a href="https://doi.org/10.1007/978-3-030-40608-0_29">On Collapsing Prefix Normal Words</a>, Language and Automata Theory and Applications (LATA 2020) LNCS Vol. 12038, Springer, Cham, 412-424.

%o (Python)

%o from itertools import product

%o def is_prefix_normal(w):

%o   for k in range(1, len(w)+1):

%o     weight0 = w[:k].count("1")

%o     for j in range(1, len(w)-k+1):

%o       weightj = w[j:j+k].count("1")

%o       if weightj > weight0: return False

%o   return True

%o def bin_pals(digits):

%o   midrange = [[""], ["0", "1"]]

%o   for p in product("01", repeat=digits//2):

%o     left = "".join(p)

%o     for middle in midrange[digits%2]:

%o       yield left+middle+left[::-1]

%o def a(n):

%o   return sum(is_prefix_normal(w) for w in bin_pals(n))

%o print([a(n) for n in range(1, 31)]) # _Michael S. Branicky_, Dec 19 2020

%Y Cf. A016116 (numbers of binary palindromes), A194850 (number of prefix normal words)

%K nonn

%O 1,1

%A _Michel Marcus_, May 29 2019

%E a(31)-a(48) from _Michael S. Branicky_, Dec 19 2020