The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A231208 Number of binary "privileged words" of length n. 3
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
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
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 Words and Sturmian Words, Ph.D. Dissertation, TUCS Dissertations 214, 2016.
EXAMPLE
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
PROG
(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
CROSSREFS
Sequence in context: A060546 A163403 A158780 * A306663 A222955 A217208
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Nov 05 2013
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
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 29 11:40 EDT 2024. Contains 372940 sequences. (Running on oeis4.)