|
|
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
|
|
|
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());
}
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|