

A330085


Length of longest binary word with the property that all distinct occurrences of identicallength 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 samelength 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 << (n1)).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



