login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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

Table of n, a(n) for n=0..45.

Gabriele Fici, Open and Closed Words, in Giovanni Pighizzini, ed., The Formal Language Theory Column, Bulletin of EATCS, 2017.

M. Forsyth, A. Jayakumar, 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.

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.

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

CROSSREFS

Cf. A235609, A297184, A297185.

Sequence in context: A016116 A060546 A163403 * A306663 A222955 A217208

Adjacent sequences:  A231205 A231206 A231207 * A231209 A231210 A231211

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 20 06:59 EDT 2021. Contains 343125 sequences. (Running on oeis4.)