The OEIS is supported by the many generous donors to the OEIS Foundation.

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.
3

%I #40 Mar 14 2024 04:57:40

%S 2,1,2,1,2,3,4,2,4,3,6,13,12,20,32,16,32,36,68,141,242,407,600,898,

%T 1440,1812,2000,2480,2176,2816,4096,2048,4096,3840,7040,13744,28272,

%U 54196,88608,160082,295624,553395,940878,1457197,2234864,3302752,4975168,7459376

%N 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.

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

%C 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.

%C 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.

%H D. Gabric, S. Holub, and J. Shallit, <a href="https://arxiv.org/abs/1903.05442">Generalized de Bruijn words and the state complexity of conjugate sets</a>, arXiv:1903.05442 [cs.FL], March 13 2019.

%e 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).

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

%Y Cf. A318687.

%K nonn

%O 1,1

%A _Jeffrey Shallit_, Aug 01 2018

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

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

Last modified September 20 20:29 EDT 2024. Contains 376078 sequences. (Running on oeis4.)