login
Length of longest binary word with the property that all distinct occurrences of identical-length blocks agree on at most n positions.
0

%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