Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #50 Jul 01 2022 22:06:07
%S 1,2,2,4,4,8,8,16,20,40,60,108,176,328,568,1040,1848,3388,6132,11332,
%T 20788,38576,71444,133256,248676,466264,875408,1649236,3112220,
%U 5888548,11160548,21198388,40329428,76865388,146720792,280498456,536986772,1029413396,1975848400,3797016444,7304942256,14068883556,27123215268,52341185672,101098109768,195444063640
%N Number of binary "privileged words" of length n.
%C 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).
%C 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
%H Gabriele Fici, <a href="http://bulletin.eatcs.org/index.php/beatcs/article/view/508">Open and Closed Words</a>, in Giovanni Pighizzini, ed., The Formal Language Theory Column, Bulletin of EATCS, 2017.
%H M. Forsyth, A. Jayakumar, and J. Shallit, <a href="http://arxiv.org/abs/1311.7403">Remarks on Privileged Words</a>, arXiv preprint arXiv:1311.7403 [cs.FL], 2013.
%H Daniel Gabric, <a href="https://arxiv.org/abs/2206.14273">Asymptotic bounds for the number of closed and privileged words</a>, arXiv:2206.14273 [math.CO], 2022.
%H J. Peltomäki, <a href="https://doi.org/10.1016/j.tcs.2013.05.028">Introducing privileged words: privileged complexity of Sturmian words</a>, Theoret. Comput. Sci. 500 (2013), 57-67.
%H J. Peltomäki, <a href="http://arxiv.org/abs/1306.6768">Privileged factors in the Thue-Morse word — a comparison of privileged words and palindromes</a>, arXiv:1306.6768 [math.CO], 2013-2015.
%H J. Peltomäki, <a href="http://www.doria.fi/handle/10024/124473">Privileged Words and Sturmian Words</a>, Ph.D. Dissertation, TUCS Dissertations 214, 2016.
%e For n = 5 the privileged words are {00000,00100,01010,01110,10001,10101,11011,11111}.
%e See A235609 for the full list of privileged words.
%e The least non-palindromic privileged word is 00101100, of length 8. - _M. F. Hasler_, Nov 05 2013
%o (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
%o (Python)
%o from itertools import count, islice, product
%o def comp(w): return "".join("2" if c == "1" else "1" for c in w)
%o def agen():
%o prev, priv = 0, set("1"); yield 1
%o for d in count(2):
%o yield 2*(len(priv) - prev)
%o prev = len(priv)
%o for p in product("12", repeat=d-1):
%o w, passes = "1" + "".join(p), False
%o if len(set(w)) == 1: passes = True
%o elif len(w.lstrip(w[0])) != len(w.rstrip(w[0])): passes = False
%o else:
%o for i in range(1, len(w)):
%o p, s = w[:i], w[-i:]
%o if p == s and p not in w[1:-1] and p in priv:
%o passes = True; break
%o if passes: priv.add(w)
%o print(list(islice(agen(), 20))) # _Michael S. Branicky_, Jul 01 2022
%Y Cf. A235609, A297184, A297185.
%K nonn
%O 0,2
%A _Jeffrey Shallit_, Nov 05 2013
%E Terms a(22) to a(30) computed by Michael Forsyth
%E More terms from Forsyth et al. (2013) added by _N. J. A. Sloane_, Jan 23 2014
%E Terms a(39)-a(45) from Peltomäki's dissertation (2016) added by _Jarkko Peltomäki_, Aug 24 2016