A231208 Number of binary "privileged words" of length n.

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

Offset: 0

Author

Jeffrey Shallit, Nov 05 2013

Keywords

• nonn

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

Examples

			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
		

Links

• Gabriele Fici, Open and Closed Words, in Giovanni Pighizzini, ed., The Formal Language Theory Column, Bulletin of EATCS, 2017.
• M. Forsyth, A. Jayakumar, and J. Shallit, Remarks on Privileged Words, arXiv preprint arXiv:1311.7403 [cs.FL], 2013.
• Daniel Gabric, Asymptotic bounds for the number of closed and privileged words, arXiv:2206.14273 [math.CO], 2022.
• J. Peltomäki, Introducing privileged words: privileged complexity of Sturmian words, Theoret. Comput. Sci. 500 (2013), 57-67.
• J. Peltomäki, Privileged factors in the Thue-Morse word — a comparison of privileged words and palindromes, arXiv:1306.6768 [math.CO], 2013-2015.
• J. Peltomäki, Privileged Words and Sturmian Words, Ph.D. Dissertation, TUCS Dissertations 214, 2016.

Crossrefs

Cf. A235609, A297184, A297185.

Programs

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)
print(list(islice(agen(), 20))) # Michael S. Branicky, Jul 01 2022

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