cp's OEIS Frontend

A305003 Number of length-n binary words having no subwords that are abelian fourth powers.

%I A305003 #27 Mar 25 2023 13:13:00
%S A305003 1,2,4,8,14,26,48,88,146,236,394,674,1060,1640,2536,4086,6470,10292,
%T A305003 16374,25720,39332,60154,92486,144218,217772,327898,494384,745096,
%U A305003 1089186,1587432,2338018,3460572,4977860,7197148,10395464,14991916,20924630,28852352
%N A305003 Number of length-n binary words having no subwords that are abelian fourth powers.
%C A305003 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).
%H A305003 Lucas Mol, <a href="/A305003/b305003.txt">Table of n, a(n) for n = 0..50</a>
%H A305003 James D. Currie, <a href="https://doi.org/10.1016/j.tcs.2004.02.005">The number of binary words avoiding abelian fourth powers grows exponentially</a>, Theoretical Computer Science 319 (2004) 441-446.  Proves that the number of such words exceeds 2^{(n-15)/16}.
%H A305003 James D. Currie, Lucas Mol, Narad Rampersad, and Jeffrey Shallit, <a href="https://arxiv.org/abs/2111.07857">Extending Dekking's construction of an infinite binary word avoiding abelian 4-powers</a>.  Proves that the number of such words of length n is Omega(1.172^n).
%H A305003 Lucas Mol, <a href="/A305003/a305003.py.txt">Python 3 program for computing a(n) for n = 2..50</a>.
%e A305003 For n = 5 the only words not counted are 00000, 00001, 10000, and their complements.
%p A305003 f:= proc(L)
%p A305003 local i, w, j;
%p A305003 for i from 1 to floor(nops(L)/4) do
%p A305003    if L[2*i]=2*L[i] and L[3*i]=3*L[i] and L[4*i]=4*L[i] then return NULL
%p A305003    fi
%p A305003 od:
%p A305003 L
%p A305003 end proc:
%p A305003 g:= proc(L)
%p A305003   local Lp;
%p A305003   Lp:= [0,op(L)]:
%p A305003   f(Lp), f(map(`+`,Lp,1));
%p A305003 end proc:
%p A305003 S:= [0]: A[0]:= 1: A[1]:= 2:for n from 2 to 31 do
%p A305003   S:= map(g, S);
%p A305003   A[n]:= 2*nops(S);
%p A305003 od:
%p A305003 seq(A[i],i=0..31); # _Robert Israel_, May 23 2018
%K A305003 nonn
%O A305003 0,2
%A A305003 _Jeffrey Shallit_, May 23 2018