Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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