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