A231208 - 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