cp's OEIS Frontend

A308465 Number of prefix normal palindromes of length n.

%I A308465 #20 Jul 02 2021 16:52:58
%S A308465 2,2,3,3,5,4,8,7,12,11,21,18,36,31,57,55,104,91,182,166,308,292,562,
%T A308465 512,1009,928,1755,1697,3247,2972,5906,5555,10506,10099,19542,18280,
%U A308465 36002,33895,64958,63045,121887,114032,226065,215377,412749,399334,778196,735941
%N A308465 Number of prefix normal palindromes of length n.
%H A308465 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 A308465 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 A308465 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 A308465 (Python)
%o A308465 from itertools import product
%o A308465 def is_prefix_normal(w):
%o A308465   for k in range(1, len(w)+1):
%o A308465     weight0 = w[:k].count("1")
%o A308465     for j in range(1, len(w)-k+1):
%o A308465       weightj = w[j:j+k].count("1")
%o A308465       if weightj > weight0: return False
%o A308465   return True
%o A308465 def bin_pals(digits):
%o A308465   midrange = [[""], ["0", "1"]]
%o A308465   for p in product("01", repeat=digits//2):
%o A308465     left = "".join(p)
%o A308465     for middle in midrange[digits%2]:
%o A308465       yield left+middle+left[::-1]
%o A308465 def a(n):
%o A308465   return sum(is_prefix_normal(w) for w in bin_pals(n))
%o A308465 print([a(n) for n in range(1, 31)]) # _Michael S. Branicky_, Dec 19 2020
%Y A308465 Cf. A016116 (numbers of binary palindromes), A194850 (number of prefix normal words)
%K A308465 nonn
%O A308465 1,1
%A A308465 _Michel Marcus_, May 29 2019
%E A308465 a(31)-a(48) from _Michael S. Branicky_, Dec 19 2020