A282133 - OEIS

%I #30 Mar 08 2023 07:49:57

%S 0,0,0,0,0,0,0,2,0,0,2,2,4,10,12,14,28,38,56,84,124,184,264,374,544,

%T 836,1190,1746,2544,3712,5410,7890,11470,16666,24436,35574,51892,

%U 75552,110124,160624,234162,341178,497058,725026,1056630,1540158,2244566,3271600

%N Number of maximal cubefree binary words of length n.

%C A word is cubefree if it has no block within it of the form xxx, where x is any nonempty block.  A cubefree word w is maximal if it cannot be extended to the right (i.e., both w0 and w1 end in cubes).

%C It appears that a(n) ~ A028445(n-11). - _M. F. Hasler_, May 05 2017

%H Lars Blomberg, <a href="/A282133/b282133.txt">Table of n, a(n) for n = 1..59</a>

%e For n = 8, the two maximal cubefree words of length 8 are 00100100 and its complement 11011011.

%e The first few maximal cubefree words beginning with 1 are:

%e [1, 1, 0, 1, 1, 0, 1, 1],

%e [1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],

%e [1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1],

%e [1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],

%e [1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1],

%e [1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],

%e [1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],

%e [1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1],

%e [1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1],

%e [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0]].

%e For those beginning with 0, take the complements. - _N. J. A. Sloane_, May 05 2017

%p # Maple code adapted from that in A286262 by _N. J. A. Sloane_, May 05 2017

%p isCubeFree:=proc(v) local n,L;

%p for n from 3 to nops(v) do for L to n/3 do

%p if v[n-L*2+1 .. n] = v[n-L*3+1 .. n-L] then RETURN(false) fi od od; true end;

%p A282133:=proc(n) local s,m;

%p s:=0;

%p for m from 2^(n-1) to 2^n-1 do

%p if isCubeFree(convert(m,base,2)) then

%p    if (not isCubeFree(convert(2*m,base,2))) and

%p    (not isCubeFree(convert(2*m+1,base,2))) then

%p    s:=s+2; fi;

%p fi;

%p od; s; end;

%p [seq(A282133(n),n=0..18)];

%t CubeFreeQ[v_List] := Module[{n, L}, For[n = 3, n <= Length[v], n++, For[L = 1, L <= n/3, L++, If[v[[n - L*2 + 1 ;; n]] == v[[n - L*3 + 1 ;; n - L]], Return[False]]]]; True];

%t a[n_] := a[n] = Module[{s, m}, s = 0; For[m = 2^(n - 1), m <= 2^n - 1, m++, If[CubeFreeQ[IntegerDigits[m, 2]], If[!CubeFreeQ[IntegerDigits[2*m, 2]] && !CubeFreeQ[IntegerDigits[2*m + 1, 2]], s += 2]]]; s];

%t Table[Print[n, " ", a[n]]; a[n], {n, 0, 25}] (* _Jean-François Alcover_, Mar 08 2023, after Maple code *)

%o (Python)

%o def icf(s): # incrementally cubefree

%o     for l in range(1, len(s)//3 + 1):

%o         if s[-3*l:-2*l] == s[-2*l:-l] == s[-l:]: return False

%o     return True

%o def aupton(nn, verbose=False):

%o     alst, cfs = [], set("0")

%o     for n in range(1, nn+1):

%o         cfsnew = set()

%o         an = 0

%o         for c in cfs:

%o             maximal = True

%o             for i in "01":

%o                 if icf(c+i):

%o                     cfsnew.add(c+i)

%o                     maximal = False

%o             if maximal: an += 2

%o         alst, cfs = alst+[an], cfsnew

%o         if verbose: print(n, an)

%o     return alst

%o print(aupton(30)) # _Michael S. Branicky_, Mar 18 2022

%Y Cf. A028445, A282317.

%Y For these numbers halved, see A286270.

%K nonn

%O 1,8

%A _Jeffrey Shallit_, Feb 06 2017

%E a(36)-a(48) from _Lars Blomberg_, Feb 09 2019