%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