|
| |
|
|
A374495
|
|
Number of palindromic periodicities among the binary words of length n.
|
|
0
|
|
|
|
2, 4, 8, 16, 32, 58, 108, 190, 336, 560, 948, 1574, 2568, 4116, 6596, 10444, 16320, 25488, 39216, 60690, 92204, 141060, 212104, 322508, 480976, 726290, 1075640, 1616368, 2380444, 3561146, 5220160, 7779754, 11359620, 16874716, 24559360, 36381264, 52797328, 78022162, 112950608
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
A binary word w is a "palindromic periodicity" if it is the prefix of the infinite word pspsps... where p and s are palindromes, not both empty, and w is at least as long as ps.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
For n = 6, the six binary words that are not palindromic periodicities are 001011, 001101, 010011, 101100, 110010, 110100.
|
|
|
PROG
|
(Python)
from itertools import product
def pal(s): return s == s[::-1]
def pp(w):
for i in range(len(w)):
if not pal(p:=w[:i]): continue
for j in range(i, len(w)+1):
if not pal(s:=w[i:j]): continue
if (ps:=p+s) == "": continue
if w == (ps*len(w))[:len(w)]: return True
return False
def a(n):
return 2*sum(1 for b in product("01", repeat=n-1) if pp("1"+"".join(b)))
(Python) # faster version that works by contruction
from itertools import count, islice, product
def binpals(d):
left, mid = product("01", repeat=d//2), [[""], "01"][d&1]
yield from ((l:="".join(t))+m+l[::-1] for t in left for m in mid)
def agen(): # generator of terms
psset = set() # {ps | p, s palindromes; ps != ""}
for n in count(1):
for i in range(n):
for p in binpals(i):
for s in binpals(n-i):
psset.add(p+s)
yield len(set((ps*n)[:n] for ps in psset))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
