A330239 Minimum circular (strong) similarity of a length-n binary word.

0, 0, 1, 2, 3, 4, 3, 4, 5, 6, 5, 6, 7, 8, 7, 8, 9, 10, 9, 10, 11, 12, 11, 12, 13, 14, 15, 14, 15, 16, 15, 16, 17, 18, 17, 18

Offset

1,4

Comments

The circular (strong) similarity of a word w is the maximum, over all nontrivial cyclic shifts x of w, of the number of positions where x and w agree.

The plausible identification of this sequence with A285869, A162330, A183041 is just illusory because a(27) = 15.

Circular (strong) similarity is basically a one-sided version of autocorrelation, where we only care about agreement of terms, not the difference between agreement and disagreement.

Links

Table of n, a(n) for n=1..36.

Michael S. Branicky, Python program

Example

For n = 7, one string achieving a(7) = 3 is 0001011.

Prog

(Python) # see links for faster version
from itertools import product
def css(k, n):
    cs = ((k>>i) | ((((1<<i)-1)&k)<<(n-i)) for i in range(1, n))
    return max(n-(k^t).bit_count() for t in cs)
def a(n): return min(css(k, n) for k in range(2**(n-1), 2**n)) if n>1 else 0
print([a(n) for n in range(1, 16)]) # Michael S. Branicky, Jan 15 2024

Crossrefs

Cf. A162330, A183041, A285869.

Sequence in context: A225320 A308937 A123066 * A235121 A270652 A326693

Adjacent sequences: A330236 A330237 A330238 * A330240 A330241 A330242

Keyword

nonn,more

Author

Jeffrey Shallit, Dec 06 2019

Extensions

a(31)-a(36) from Michael S. Branicky, Jan 15 2024

Status

approved