|
|
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 non-palindromic 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^(n-1)-2, 2^(n-1)+1, 2^n-1], w)&&return(1); for(i=1, n-2, (w-p=w>>i)%2^(n-i)&&next; for(j=1, i-1, (w>>j-p)%2^(n-i)||next(2)); isp(p, n-i)&&return(1))); sum(i=1, 2^(n-1)-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=d-1):
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
|
|
|
|