login
Number of length-n binary words containing no antisquares except 01 and 10.
1

%I #14 Jan 06 2021 19:38:55

%S 1,2,4,8,12,20,30,46,72,112,164,248,364,542,796,1180,1732,2550,3744,

%T 5504,8076,11854,17386,25498,37382,54808,80342,117770,172618,253008,

%U 370820,543490,796546,1167424,1710966,2507572,3675050,5386080,7893712,11568832,16954976

%N Number of length-n binary words containing no antisquares except 01 and 10.

%C An antisquare is a word of the form x x', where x' is the bitwise complement of x.

%H Michael S. Branicky, <a href="/A307732/b307732.txt">Table of n, a(n) for n = 0..52</a>

%e For n = 4 the 12 examples are all length-4 binary words except 0011, 0110, 1001, and 1100.

%o (Python)

%o from numba import njit

%o @njit

%o def aupto(nn, v=False):

%o alst = [1, 2, 4, 8]

%o if nn <= 4: return alst[:nn+1]

%o n, prev_as = 4, [0, 1, 2, 3] # |w|=3, w0 = 0, no a.s.'s except 01, 10

%o while n <= nn:

%o new_as = []

%o for w in prev_as:

%o for b in [0, 1]:

%o wb = 2*w + b

%o for k in range(2, n//2+1):

%o mask2 = (1<<k) - 1

%o mask1 = mask2 << k

%o if (wb&mask2)^((wb&mask1)>>k)==mask2: break # wb ends with an a.s.

%o else: new_as.append(wb) # no break

%o alst.append(2*len(new_as)) # twice that starting with 0 by symmetry

%o if v: print(n, 2*len(new_as), alst)

%o prev_as = new_as

%o n += 1

%o return alst

%o print(aupto(30)) # _Michael S. Branicky_, Jan 06 2021

%K nonn,base

%O 0,2

%A _Jeffrey Shallit_, Apr 25 2019

%E a(36) and beyond from _Michael S. Branicky_, Jan 06 2021