|
|
A282133
|
|
Number of maximal cubefree binary words of length n.
|
|
5
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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).
|
|
LINKS
|
|
|
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
|
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;
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;
|
|
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];
|
|
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
|
|
CROSSREFS
|
For these numbers halved, see A286270.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|