A297184 -id:A297184 - cp's OEIS frontend

A226452 Number of closed binary words of length n.

1, 2, 2, 4, 6, 12, 20, 36, 62, 116, 204, 364, 664, 1220, 2240, 4132, 7646, 14244, 26644, 49984, 94132, 177788, 336756, 639720, 1218228, 2325048, 4446776, 8520928, 16356260, 31447436, 60552616, 116753948, 225404486, 435677408, 843029104, 1632918624, 3165936640

Offset: 0

Jeffrey Shallit, Jun 07 2013

nonn

A word is closed if it contains a proper factor that occurs both as a prefix and as a suffix but does not have internal occurrences.

a(n+1) <= 2*a(n); for n > 1: a(n) <= A094536(n). - Reinhard Zumkeller, Jun 15 2013

			a(4) = 6 because the only closed binary words of length 4 are 0000, 0101, 0110, and their complements.

Lars Blomberg, Table of n, a(n) for n = 0..38
Michael S. Branicky, Python program
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.
Daniel Gabric, Asymptotic bounds for the number of closed and privileged words, arXiv:2206.14273 [math.CO], 2022.

Cf. A297183, A297184, A297185.

import Data.List (inits, tails, isInfixOf)
a226452 n = a226452_list !! n
a226452_list = 1 : 2 : f [[0,0],[0,1],[1,0],[1,1]] where
   f bss = sum (map h bss) : f ((map (0 :) bss) ++ (map (1 :) bss)) where
   h bs = fromEnum $ or $ zipWith
           (\xs ys -> xs == ys && not (xs `isInfixOf` (init $ tail bs)))
           (init $ inits bs) (reverse $ tails $ tail bs)
-- Reinhard Zumkeller, Jun 15 2013

# see link for faster, bit-based version
from itertools import product
def closed(w): # w is a closed word
    if len(set(w)) <= 1: return True
    for l in range(1, len(w)):
        if w[:l] == w[-l:] and w[:l] not in w[1:-1]:
            return True
    return False
def a(n):
    if n == 0: return 1
    return 2*sum(closed("0"+"".join(b)) for b in product("01", repeat=n-1))
print([a(n) for n in range(22)]) # Michael S. Branicky, Jul 09 2022

a(17)-a(23) from Reinhard Zumkeller, Jun 15 2013

a(24)-a(36) from Lars Blomberg, Dec 28 2015

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

Original entry on oeis.org

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

Jeffrey Shallit, Nov 05 2013

nonn

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

			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

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.

Cf. A235609, A297184, A297185.

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

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

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

cp's OEIS Frontend

A226452 Number of closed binary words of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Python

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Extensions

A297185 One-half of the number of closed binary words of length n that are not privileged.

Views

Author

Keywords

Comments

Crossrefs