%I #46 Mar 26 2023 02:12:34

%S 1,3,9,24,66,180,468,1206,3150,7998,20124,50520,124044,303906,744870,

%T 1790226,4319322,10432044,24926934,59570514,142662384,339247320,

%U 807092274,1920506232,4543861644

%N Number of Abelian cubefree words over a 3-letter alphabet.

%C An abelian cube is three consecutive blocks that are anagrams (rearrangements) of each other, such as (012)(120)(102).

%C For n > 1, a(n) is a multiple of 3 by symmetry. - _Michael S. Branicky_, Jul 11 2021

%H A. Aberkane, J. D. Currie and N. Rampersad, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Currie/currie18.html">The Number of Ternary Words Avoiding Abelian Cubes Grows Exponentially</a>, J. Integer Sequences, Article 04.2.7, 2004.

%H A. V. Samsonov and A. M. Shur, <a href="http://dx.doi.org/10.1051/ita/2011127">On Abelian repetition threshold</a>, RAIRO-Theor. Inf. Appl. 46 (2012) 147-163.

%F Let L = lim a(n)^(1/n); then L exists since a(n) is submultiplicative. L > 2^(1/24) (Aberkane, Currie, Rampersad 2004), L < 2.371237 (Samsonov, Shur 2012). No good empirical guess for L is known. - _Arseny Shur_, Apr 27 2015

%F A305595(n) <= a(n) <= A051042(n). - _Michael S. Branicky_, Jul 11 2021

%e a(3) = 24, since the only Abelian cubes of length 3 are 000, 111, 222.

%o (Python)

%o from itertools import product

%o def anagrams(b1, b2, b3):

%o return sorted(b1) == sorted(b2) == sorted(b3)

%o def acf(s):

%o for l in range(1, len(s)//3 + 1):

%o for i in range(len(s) - 3*l + 1):

%o if anagrams(s[i:i+l], s[i+l:i+2*l], s[i+2*l:i+3*l]): return False

%o return True

%o def a(n):

%o if n == 0: return 1

%o return 3*sum(acf("0"+"".join(w)) for w in product("012", repeat=n-1))

%o print([a(n) for n in range(14)]) # _Michael S. Branicky_, Jul 11 2021

%o (Python) # faster, but > memory, version for initial segment of sequence

%o def anagrams(b1, b2, b3): return sorted(b1) == sorted(b2) == sorted(b3)

%o def iacf(s): # incrementally abelian cubefree

%o for l in range(1, len(s)//3 + 1):

%o if anagrams(s[-3*l:-2*l], s[-2*l:-l], s[-l:]): return False

%o return True

%o def aupton(nn, verbose=False):

%o alst, acfs = [1], set("0")

%o for n in range(1, nn+1):

%o an = 3*len(acfs)

%o acfsnew = set(c+i for c in acfs for i in "012" if iacf(c+i))

%o alst, acfs = alst+[an], acfsnew

%o if verbose: print(n, an)

%o return alst

%o print(aupton(14)) # _Michael S. Branicky_, Jul 22 2021

%Y Cf. A051042, A305595.

%K nonn,hard,more

%O 0,2

%A _Jeffrey Shallit_, Jun 19 2004

%E More terms from _Jeffrey Shallit_, May 23 2018

%E a(19)-a(21) from _Michael S. Branicky_, Jul 22 2021

%E a(22)-a(24) from _Michael S. Branicky_, Mar 25 2023