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,8

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

Links

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

Example

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

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

Prog

(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

Crossrefs

Cf. A028445, A282317.

For these numbers halved, see A286270.

Sequence in context: A033737 A033747 A087611 * A338819 A153869 A128541

Adjacent sequences: A282130 A282131 A282132 * A282134 A282135 A282136

Keyword

nonn,changed

Author

Jeffrey Shallit, Feb 06 2017

Extensions

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

Status

approved