The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A330085 Length of longest binary word with the property that all distinct occurrences of identical-length blocks agree on at most n positions. 0
 2, 4, 7, 9, 12, 14, 16, 19, 21, 23, 26, 28, 30, 32, 34, 37, 39, 41, 43, 45 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,1 COMMENTS By "distinct occurrences" we do not mean that the blocks themselves must be distinct, but rather that they begin at different positions. 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. LINKS Table of n, a(n) for n=0..19. EXAMPLE The lexicographically least longest words for n = 0, 1, ..., 10 are as follows: 0: 01 1: 0010 2: 0011010 3: 001010011 4: 001101010011 5: 00011010100110 6: 0010100110001011 7: 0011010011101010011 8: 000110100111010100110 9: 00100110100011100101011 10: 01011000111011000101100101 11: 0001110100100110101011000110 12: 001010011011000101110001101011 PROG (Rust) fn max_length(n: u32, l: u32, x: u64) -> u32 { (0..2).map(|lowbit| (x << 1) | lowbit) .filter(|x| !(n + 1..l + 1).any(|b| (1..l + 1 - b + 1) .any(|occ| (!(x ^ (x >> occ)) & ((1u64 << b) - 1)).count_ones() > n))) .map(|x| max_length(n, l + 1, x)) .max().unwrap_or(l) } fn main() { for n in 1..64 { println!("{} {}", n, (1..=1u64 << (n-1)).map(|x| max_length(n, n, x)).max().unwrap()); } } // Falk Hüffner, Jan 31 2020 CROSSREFS Sequence in context: A287074 A304501 A283964 * A175884 A003151 A189939 Adjacent sequences: A330082 A330083 A330084 * A330086 A330087 A330088 KEYWORD nonn,more AUTHOR Jeffrey Shallit, Dec 01 2019 EXTENSIONS a(13)-a(19) from Falk Hüffner, Jan 31 2020 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 12 10:21 EDT 2024. Contains 375092 sequences. (Running on oeis4.)