A051042 Number of ternary cubefree words of length n.

1, 3, 9, 24, 66, 180, 486, 1314, 3558, 9606, 25956, 70134, 189462, 511866, 1382880, 3735888, 10092762, 27266340, 73661610, 199001490, 537615066, 1452399978, 3923748270

Offset

0,2

Links

Table of n, a(n) for n=0..22.

A. M. Shur, Growth properties of power-free languages, Computer Science Review, Vol. 6 (2012), 187-208.

A. M. Shur, Numerical values of the growth rates of power-free languages, arXiv:1009.4415 [cs.FL], 2010.

Eric Weisstein's World of Mathematics, Cubefree Word.

Formula

Let L = lim a(n)^(1/n); then L exists since a(n) is submultiplicative. 2.7015614 < L < 2.7015616 (Shur 2012); the gap between the bounds can be made less than any given constant. - Arseny Shur, Apr 27 2015

Example

There are 81 ternary words of length 4. Five of them contain the cube 000: 0000, 0001, 0002, 1000, 2000; same for 111 and 222. So, a(4)=81-3*5=66. - Arseny Shur, Apr 27 2015

Prog

(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]*2 == s[i+l:i+3*l]: return False
  return True
def a(n):
  if n == 0: return 1
  return 3*sum(cf("0"+"".join(w)) for w in product("012", repeat=n-1))
print([a(n) for n in range(14)]) # Michael S. Branicky, Apr 16 2021

Crossrefs

Cf. A028445.

Sequence in context: A153582 A269461 A096168 * A121907 A179176 A118771

Adjacent sequences: A051039 A051040 A051041 * A051043 A051044 A051045

Keyword

nonn

Author

Eric W. Weisstein

Extensions

More terms from Sascha Kurz, Mar 22 2002

a(19)-a(22) from Michael S. Branicky, Apr 16 2021

Status

approved