A330239 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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