

A231208


Number of binary "privileged words" of length n.


3



1, 2, 2, 4, 4, 8, 8, 16, 20, 40, 60, 108, 176, 328, 568, 1040, 1848, 3388, 6132, 11332, 20788, 38576, 71444, 133256, 248676, 466264, 875408, 1649236, 3112220, 5888548, 11160548, 21198388, 40329428, 76865388, 146720792, 280498456, 536986772, 1029413396, 1975848400, 3797016444, 7304942256, 14068883556, 27123215268, 52341185672, 101098109768, 195444063640
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

A word w is "privileged" if it is of length <= 1, or if it has a privileged prefix that appears exactly twice in w, once as a prefix and once as a suffix (which may overlap).
All terms beyond a(0) are even because the 1's complement of a privileged word is again privileged (and different).  M. F. Hasler, Nov 05 2013


LINKS

Gabriele Fici, Open and Closed Words, in Giovanni Pighizzini, ed., The Formal Language Theory Column, Bulletin of EATCS, 2017.


EXAMPLE

For n = 5 the privileged words are {00000,00100,01010,01110,10001,10101,11011,11111}.
See A235609 for the full list of privileged words.
The least nonpalindromic privileged word is 00101100, of length 8.  M. F. Hasler, Nov 05 2013


PROG

(PARI) A231208=n>{local(isp(w, n, p)=setsearch([0, 2^(n1)2, 2^(n1)+1, 2^n1], w)&&return(1); for(i=1, n2, (wp=w>>i)%2^(ni)&&next; for(j=1, i1, (w>>jp)%2^(ni)next(2)); isp(p, ni)&&return(1))); sum(i=1, 2^(n1)1, isp(i, n), 1)*2!n} \\ M. F. Hasler, Nov 05 2013
(Python)
from itertools import count, islice, product
def comp(w): return "".join("2" if c == "1" else "1" for c in w)
def agen():
prev, priv = 0, set("1"); yield 1
for d in count(2):
yield 2*(len(priv)  prev)
prev = len(priv)
for p in product("12", repeat=d1):
w, passes = "1" + "".join(p), False
if len(set(w)) == 1: passes = True
elif len(w.lstrip(w[0])) != len(w.rstrip(w[0])): passes = False
else:
for i in range(1, len(w)):
p, s = w[:i], w[i:]
if p == s and p not in w[1:1] and p in priv:
passes = True; break
if passes: priv.add(w)


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS

Terms a(22) to a(30) computed by Michael Forsyth
More terms from Forsyth et al. (2013) added by N. J. A. Sloane, Jan 23 2014
Terms a(39)a(45) from Peltomäki's dissertation (2016) added by Jarkko Peltomäki, Aug 24 2016


STATUS

approved



