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

Author

Jeffrey Shallit, Dec 06 2019

Keywords

• nonn
• more

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.

Examples

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

Links

• Michael S. Branicky, Python program

Crossrefs

Cf. A162330, A183041, A285869.

Programs

Python

# see links for faster version
from itertools import product
def css(k, n):
    cs = ((k>>i) | ((((1<1 else 0
print([a(n) for n in range(1, 16)]) # Michael S. Branicky, Jan 15 2024

Extensions

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