cp's OEIS Frontend

A282133 Number of maximal cubefree binary words of length n.

%I A282133 #35 Nov 21 2024 05:16:07
%S A282133 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 A282133 836,1190,1746,2544,3712,5410,7890,11470,16666,24436,35574,51892,
%U A282133 75552,110124,160624,234162,341178,497058,725026,1056630,1540158,2244566,3271600
%N A282133 Number of maximal cubefree binary words of length n.
%C A282133 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 A282133 It appears that a(n) ~ A028445(n-11). - _M. F. Hasler_, May 05 2017
%H A282133 Lars Blomberg, <a href="/A282133/b282133.txt">Table of n, a(n) for n = 1..59</a>
%e A282133 For n = 8, the two maximal cubefree words of length 8 are 00100100 and its complement 11011011.
%e A282133 The first few maximal cubefree words beginning with 1 are:
%e A282133 [1, 1, 0, 1, 1, 0, 1, 1],
%e A282133 [1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],
%e A282133 [1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1],
%e A282133 [1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],
%e A282133 [1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1],
%e A282133 [1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],
%e A282133 [1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
%e A282133 [1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1],
%e A282133 [1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1],
%e A282133 [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0].
%e A282133 For those beginning with 0, take the complements. - _N. J. A. Sloane_, May 05 2017
%p A282133 # Maple code adapted from that in A286262 by _N. J. A. Sloane_, May 05 2017
%p A282133 isCubeFree:=proc(v) local n,L;
%p A282133 for n from 3 to nops(v) do for L to n/3 do
%p A282133 if v[n-L*2+1 .. n] = v[n-L*3+1 .. n-L] then RETURN(false) fi od od; true end;
%p A282133 A282133:=proc(n) local s,m;
%p A282133 s:=0;
%p A282133 for m from 2^(n-1) to 2^n-1 do
%p A282133 if isCubeFree(convert(m,base,2)) then
%p A282133    if (not isCubeFree(convert(2*m,base,2))) and
%p A282133    (not isCubeFree(convert(2*m+1,base,2))) then
%p A282133    s:=s+2; fi;
%p A282133 fi;
%p A282133 od; s; end;
%p A282133 [seq(A282133(n),n=0..18)];
%t A282133 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 A282133 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 A282133 Table[Print[n, " ", a[n]]; a[n], {n, 0, 25}] (* _Jean-François Alcover_, Mar 08 2023, after Maple code *)
%o A282133 (Python)
%o A282133 def icf(s): # incrementally cubefree
%o A282133     for l in range(1, len(s)//3 + 1):
%o A282133         if s[-3*l:-2*l] == s[-2*l:-l] == s[-l:]: return False
%o A282133     return True
%o A282133 def aupton(nn, verbose=False):
%o A282133     alst, cfs = [], set("0")
%o A282133     for n in range(1, nn+1):
%o A282133         cfsnew = set()
%o A282133         an = 0
%o A282133         for c in cfs:
%o A282133             maximal = True
%o A282133             for i in "01":
%o A282133                 if icf(c+i):
%o A282133                     cfsnew.add(c+i)
%o A282133                     maximal = False
%o A282133             if maximal: an += 2
%o A282133         alst, cfs = alst+[an], cfsnew
%o A282133         if verbose: print(n, an)
%o A282133     return alst
%o A282133 print(aupton(30)) # _Michael S. Branicky_, Mar 18 2022
%Y A282133 Cf. A028445, A282317.
%Y A282133 For these numbers halved, see A286270.
%K A282133 nonn
%O A282133 1,8
%A A282133 _Jeffrey Shallit_, Feb 06 2017
%E A282133 a(36)-a(48) from _Lars Blomberg_, Feb 09 2019