A231208 -id:A231208 - cp's OEIS frontend

A297184 Number of closed binary words of length n that are not privileged.

0, 0, 0, 0, 2, 4, 12, 20, 42, 76, 144, 256, 488, 892, 1672, 3092, 5798, 10856, 20512, 38652, 73344, 139212, 265312, 506464, 969552, 1858784, 3571368, 6871692, 13244040, 25558888, 49392068, 95555560, 185075058, 358812020, 696308312, 1352420168, 2628949868

Offset: 0

N. J. A. Sloane, Dec 28 2017

nonn

G. Badkobeh, G. Fici, Z. Lipták, On the number of closed factors in a word, in A.-H. Dediu et al., eds., LATA 2015, LNCS 8977, 2015, pp. 381-390. Available at arXiv, arXiv:1305.6395 [cs.FL], 2013-2014.
Gabriele Fici, Open and Closed Words, in Giovanni Pighizzini, ed., The Formal Language Theory Column, Bulletin of EATCS, 2017.

Equals A226452-A231208.

Cf. A297185.

A235609 List of privileged words over the alphabet {1,2}.

Original entry on oeis.org

1, 2, 11, 22, 111, 121, 212, 222, 1111, 1221, 2112, 2222, 11111, 11211, 12121, 12221, 21112, 21212, 22122, 22222, 111111, 112211, 121121, 122221, 211112, 212212, 221122, 222222, 1111111, 1112111, 1121211, 1122211, 1211121, 1212121, 1221221, 1222221, 2111112

Offset: 1

N. J. A. Sloane, Jan 23 2014

nonn

"A word w is privileged if (a) it has length <= 1, or (b) it has a privileged border that appears exactly twice in w." - from the Forsyth et al. paper.

The first terms which differ from "palindromes over the alphabet {1,2}" (not in the OEIS) are the four 8 digit terms a({48, 49, 60, 61}) = {11212211, 11221211, 22112122, 22121122}, then come 9 digit terms a(71) = 112122211, etc. The first palindromes not in the sequence are the 14-digit terms {11212211221211, 11221211212211, 22112122121122, 22121122112122}. - M. F. Hasler, Nov 02 2020

Michael S. Branicky, Table of n, a(n) for n = 1..13752 (terms with <= 18 digits; terms 1..4232 from Lars Blomberg)
M. Forsyth, A. Jayakumar, and J. Shallit, Remarks on Privileged Words, arXiv preprint arXiv:1311.7403 [cs.FL], 2013.
J. Peltomäki, Introducing privileged words: privileged complexity of Sturmian words, Theoret. Comput. Sci. 500 (2013), 57-67.

A231208 gives the number of privileged words of given length.

Subsequence of A007931 (numbers having only digits 1 & 2).

is_A235609(w, n, p)={n || if(#setminus(Set(p=digits(w)),[1,2]), return, w=fromdigits([d-1|d<-p],2); n=#p; p[1]>1 && w=2^n-1-w); !w|| setsearch([2^(n-1)-2, 2^(n-1)+1, 2^n-1], w)|| 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)); is_A235609(p, n-i)&&return(1))} \\ M. F. Hasler, Nov 02 2020

from itertools import count, islice, product
def comp(w): return "".join("2" if c == "1" else "1" for c in w)
def agen():
    priv = set("1"); yield from [1, 2]
    for d in count(2):
        found = []
        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: found.append(w); priv.add(w)
        yield from (int(w) for w in found)
        yield from sorted(int(comp(w)) for w in found)
print(list(islice(agen(), 37))) # Michael S. Branicky, Jul 01 2022

a(29)-a(37) from Lars Blomberg, Jun 16 2017

cp's OEIS Frontend

A297184 Number of closed binary words of length n that are not privileged.

Views

Author

Keywords

Links

Crossrefs

A235609 List of privileged words over the alphabet {1,2}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

Extensions