OFFSET
0,2
COMMENTS
An "abelian fourth power" means four contiguous nonempty blocks of the same length and same number of 0's and 1's, such as (011)(101)(110)(101).
LINKS
Lucas Mol, Table of n, a(n) for n = 0..50
James D. Currie, The number of binary words avoiding abelian fourth powers grows exponentially, Theoretical Computer Science 319 (2004) 441-446. Proves that the number of such words exceeds 2^{(n-15)/16}.
James D. Currie, Lucas Mol, Narad Rampersad, and Jeffrey Shallit, Extending Dekking's construction of an infinite binary word avoiding abelian 4-powers. Proves that the number of such words of length n is Omega(1.172^n).
EXAMPLE
For n = 5 the only words not counted are 00000, 00001, 10000, and their complements.
MAPLE
f:= proc(L)
local i, w, j;
for i from 1 to floor(nops(L)/4) do
if L[2*i]=2*L[i] and L[3*i]=3*L[i] and L[4*i]=4*L[i] then return NULL
fi
od:
L
end proc:
g:= proc(L)
local Lp;
Lp:= [0, op(L)]:
f(Lp), f(map(`+`, Lp, 1));
end proc:
S:= [0]: A[0]:= 1: A[1]:= 2:for n from 2 to 31 do
S:= map(g, S);
A[n]:= 2*nops(S);
od:
seq(A[i], i=0..31); # Robert Israel, May 23 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, May 23 2018
STATUS
approved