|
%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
|
