|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
LINKS
|
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))
|
|
CROSSREFS
|
Cf. A016116 (numbers of binary palindromes), A194850 (number of prefix normal words)
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|