|
%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
|
