|
%I #24 Jan 31 2020 07:32:04
%S 2,4,7,9,12,14,16,19,21,23,26,28,30,32,34,37,39,41,43,45
%N Length of longest binary word with the property that all distinct occurrences of identical-length blocks agree on at most n positions.
%C By "distinct occurrences" we do not mean that the blocks themselves must be distinct, but rather that they begin at different positions.
%C Alternatively, this sequence counts the length of the longest binary word w in which each prefix of w matches its corresponding same-length suffix of w in at most n positions.
%e The lexicographically least longest words for n = 0, 1, ..., 10 are as follows:
%e 0: 01
%e 1: 0010
%e 2: 0011010
%e 3: 001010011
%e 4: 001101010011
%e 5: 00011010100110
%e 6: 0010100110001011
%e 7: 0011010011101010011
%e 8: 000110100111010100110
%e 9: 00100110100011100101011
%e 10: 01011000111011000101100101
%e 11: 0001110100100110101011000110
%e 12: 001010011011000101110001101011
%o (Rust) fn max_length(n: u32, l: u32, x: u64) -> u32 {
%o (0..2).map(|lowbit| (x << 1) | lowbit)
%o .filter(|x| !(n + 1..l + 1).any(|b| (1..l + 1 - b + 1)
%o .any(|occ| (!(x ^ (x >> occ)) & ((1u64 << b) - 1)).count_ones() > n)))
%o .map(|x| max_length(n, l + 1, x))
%o .max().unwrap_or(l)
%o }
%o fn main() {
%o for n in 1..64 {
%o println!("{} {}", n, (1..=1u64 << (n-1)).map(|x| max_length(n, n, x)).max().unwrap());
%o }
%o } // _Falk Hüffner_, Jan 31 2020
%K nonn,more
%O 0,1
%A _Jeffrey Shallit_, Dec 01 2019
%E a(13)-a(19) from _Falk Hüffner_, Jan 31 2020
| 