login
A330239
Minimum circular (strong) similarity of a length-n binary word.
1
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
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
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Dec 06 2019
EXTENSIONS
a(31)-a(36) from Michael S. Branicky, Jan 15 2024
STATUS
approved