A282133 Number of maximal cubefree binary words of length n.

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, 836, 1190, 1746, 2544, 3712, 5410, 7890, 11470, 16666, 24436, 35574, 51892, 75552, 110124, 160624, 234162, 341178, 497058, 725026, 1056630, 1540158, 2244566, 3271600

Offset: 1

Author

Jeffrey Shallit, Feb 06 2017

Keywords

• nonn

Comments

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).

It appears that a(n) ~ A028445(n-11). - M. F. Hasler, May 05 2017

Examples

			For n = 8, the two maximal cubefree words of length 8 are 00100100 and its complement 11011011.
The first few maximal cubefree words beginning with 1 are:
[1, 1, 0, 1, 1, 0, 1, 1],
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],
[1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1],
[1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],
[1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1],
[1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],
[1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
[1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1],
[1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0].
For those beginning with 0, take the complements. - _N. J. A. Sloane_, May 05 2017
		

Links

• Lars Blomberg, Table of n, a(n) for n = 1..59

Crossrefs

Cf. A028445, A282317.

For these numbers halved, see A286270.

Programs

Maple

# Maple code adapted from that in A286262 by N. J. A. Sloane, May 05 2017
isCubeFree:=proc(v) local n,L;
for n from 3 to nops(v) do for L to n/3 do
if v[n-L*2+1 .. n] = v[n-L*3+1 .. n-L] then RETURN(false) fi od od; true end;
A282133:=proc(n) local s,m;
s:=0;
for m from 2^(n-1) to 2^n-1 do
if isCubeFree(convert(m,base,2)) then
   if (not isCubeFree(convert(2*m,base,2))) and
   (not isCubeFree(convert(2*m+1,base,2))) then
   s:=s+2; fi;
fi;
od; s; end;
[seq(A282133(n),n=0..18)];

Mathematica

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];
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];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 08 2023, after Maple code *)

Python

def icf(s): # incrementally cubefree
    for l in range(1, len(s)//3 + 1):
        if s[-3*l:-2*l] == s[-2*l:-l] == s[-l:]: return False
    return True
def aupton(nn, verbose=False):
    alst, cfs = [], set("0")
    for n in range(1, nn+1):
        cfsnew = set()
        an = 0
        for c in cfs:
            maximal = True
            for i in "01":
                if icf(c+i):
                    cfsnew.add(c+i)
                    maximal = False
            if maximal: an += 2
        alst, cfs = alst+[an], cfsnew
        if verbose: print(n, an)
    return alst
print(aupton(30)) # Michael S. Branicky, Mar 18 2022

Extensions

a(36)-a(48) from Lars Blomberg, Feb 09 2019