login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A317586 Number of circular binary words of length n having the maximum possible number of distinct blocks of length floor(log_2 n) and floor(log_2 n)+1. 2
2, 1, 2, 1, 2, 3, 4, 2, 4, 3, 6, 13, 12, 20, 32, 16, 32, 36, 68, 141, 242, 407, 600, 898, 1440, 1812, 2000, 2480, 2176, 2816, 4096, 2048, 4096, 3840, 7040, 13744, 28272, 54196, 88608, 160082, 295624, 553395, 940878, 1457197, 2234864, 3302752, 4975168, 7459376 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

A circular binary word (a.k.a. "necklace") can be viewed as a representative of the equivalence class under cyclic shift.

The words counted by this sequence have 2^i distinct blocks of length i = floor(log_2 n) and n distinct blocks of length i+1.

This sequence counts a certain natural generalization of de Bruijn words, which are cyclic words of length 2^n containing all n-bit blocks as subwords.

LINKS

Table of n, a(n) for n=1..48.

D. Gabric, S. Holub, and J. Shallit, Generalized de Bruijn words and the state complexity of conjugate sets, arXiv:1903.05442 [cs.FL], March 13 2019.

EXAMPLE

For n = 6 the 3 possibilities are {000111, 001011, 001101}.  Each contains all 4 blocks of length 2, and 6 distinct blocks of length 3 (when considered circularly).

CROSSREFS

Cf. A016031, which gives the value of this sequence evaluated at powers of 2.

Cf. A318687.

Sequence in context: A069003 A087855 A083409 * A303780 A234022 A261273

Adjacent sequences:  A317583 A317584 A317585 * A317587 A317588 A317589

KEYWORD

nonn,more

AUTHOR

Jeffrey Shallit, Aug 01 2018

EXTENSIONS

Terms a(33) - a(48) provided by Štěpán Holub

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 August 21 06:14 EDT 2019. Contains 326162 sequences. (Running on oeis4.)