A179677 Number of binary sequences of length n having exactly one conjugate at Hamming distance 2

0, 2, 0, 0, 0, 12, 0, 32, 0, 140, 0, 264, 0, 868, 0, 1792, 0, 4464, 0, 9560, 0, 22484, 0, 47328, 0, 106444, 0, 225736, 0, 490380, 0, 1040384, 0, 2228156, 0, 4698144, 0, 9961396, 0, 20930080, 0, 44034564

Offset

1,2

Comments

The conjugate of a binary sequence is a cyclic shift. For example, 001011 and 110010 are conjugates because if you rotate the first 4 places to the left, you get the second.

The Hamming distance is the number of bits that are different.

It appears that a(2*p) = 4*p*(2^(p-2)-1), for p prime. - Giovanni Resta, Jul 09 2018

Links

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

Jeffrey Shallit, Hamming distance for conjugates, Discrete Mathematics 309(12): 4197-4199 (2009).

Example

a(6) = 12, with examples being 001011, 001101, 010011, 010110, 011001, 011010, and their complements (0's and 1's interchanged).  The conjugates of 001011 are: 010110, 101100, 011001, 110010, and 100101, which have Hamming distances 4, 4, 2, 4, and 4, respectively, so exactly one has distance 2.

Prog

(Python)
from itertools import product
def h(w, x): return sum(1 for wi, xi in zip(w, x) if wi != xi)
def ok(w):
    c = 0
    for s in range(1, len(w)):
        if h(w, w[s:]+w[:s]) == 2:
            c += 1
            if c == 2:
                return False
    return c == 1
def a(n):
    return 2*sum(1 for p in product("01", repeat=n-1) if ok("0"+"".join(p)))
print([a(n) for n in range(1, 19)]) # Michael S. Branicky, Mar 14 2022

Crossrefs

Sequence in context: A348030 A287466 A288014 * A250397 A348029 A224074

Adjacent sequences: A179674 A179675 A179676 * A179678 A179679 A179680

Keyword

nonn,more

Author

Jeffrey Shallit, Jan 09 2011

Extensions

a(17)-a(40) from Falk Hüffner, Jul 08 2018

a(41)-a(42) from Giovanni Resta, Jul 09 2018

Status

approved