login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A305003 Number of length-n binary words having no subwords that are abelian fourth powers. 2
1, 2, 4, 8, 14, 26, 48, 88, 146, 236, 394, 674, 1060, 1640, 2536, 4086, 6470, 10292, 16374, 25720, 39332, 60154, 92486, 144218, 217772, 327898, 494384, 745096, 1089186, 1587432, 2338018, 3460572, 4977860, 7197148, 10395464, 14991916, 20924630, 28852352 (list; graph; refs; listen; history; text; internal format)
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
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
Sequence in context: A317884 A365253 A054193 * A117633 A308148 A273154
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, May 23 2018
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 13:25 EDT 2024. Contains 371254 sequences. (Running on oeis4.)