|
|
A028445
|
|
Number of cubefree words of length n on two letters.
|
|
20
|
|
|
1, 2, 4, 6, 10, 16, 24, 36, 56, 80, 118, 174, 254, 378, 554, 802, 1168, 1716, 2502, 3650, 5324, 7754, 11320, 16502, 24054, 35058, 51144, 74540, 108664, 158372, 230800, 336480, 490458, 714856, 1041910, 1518840, 2213868, 3226896, 4703372, 6855388, 9992596
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
It appears that the number of maximal cubefree words A282133(n) ~ a(n-11). - M. F. Hasler, May 05 2017
|
|
REFERENCES
|
S. R. Finch, Mathematical Constants, Cambridge, 2003, see page 368 for cubefree words.
|
|
LINKS
|
Anne E. Edlin, Cubefree words [Cached copy, pdf version, with permission]
|
|
FORMULA
|
Let L = lim a(n)^(1/n); then L exists since a(n) is submultiplicative, and 1.4575732 < L < 1.4575772869240 (Shur 2010). Empirical: L=1.4575772869237..., i.e. the upper bound is very precise. - Arseny Shur, Apr 27 2015
|
|
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;
if n=0 then 1 else add( `if`(isCubeFree(convert(m, base, 2)), 2, 0), m = 2^(n-1)..2^n-1) fi end;
|
|
MATHEMATICA
|
Length/@NestList[DeleteCases[Flatten[Outer[Append, #, {0, 1}, 1], 1], {___, x__, x__, x__, ___}] &, {{}}, 20] (* Vladimir Reshetnikov, May 16 2016 *)
|
|
PROG
|
(PARI) (isCubeFree(v)=!for(n=3, #v, for(L=1, n\3, v[n-L*2+1..n]==v[n-L*3+1..n-L]&&return))); A028445(n)=sum(m=1<<(n-1)+1<<(n-4), 1<<n-1<<(n-3)-1, isCubeFree(binary(m)))<<!!n \\ Becomes slow beyond n=20. - M. F. Hasler, May 04 2017
(Python)
from itertools import product
def cf(s):
for l in range(1, len(s)//3 + 1):
for i in range(len(s) - 3*l + 1):
if s[i:i+l] == s[i+l:i+2*l] == s[i+2*l:i+3*l]: return False
return True
def a(n):
if n == 0: return 1
return 2*sum(1 for w in product("01", repeat=n-1) if cf("0"+"".join(w)))
(Python) # faster, but > memory, version for initial segment of sequence
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 = [1], set("0")
for n in range(1, nn+1):
an = 2*len(cfs)
cfsnew = set(c+i for c in cfs for i in "01" if icf(c+i))
alst, cfs = alst+[an], cfsnew
if verbose: print(n, an)
return alst
|
|
CROSSREFS
|
A282133 gives the maximally cubefree words.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Anne Edlin (anne(AT)euclid.math.temple.edu)
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|