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
`

Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents

The OEIS Community | Maintained by The OEIS Foundation Inc.