|
|
A278709
|
|
Smallest number k such that each binary string of length at least k contains an abelian square of order at least n.
|
|
0
|
|
|
4, 11, 19, 27, 35, 43, 51, 63, 77, 91, 107
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
In this context, a square is a repetition of one or more digits like 11 or 101101. An abelian square allows digits in each factor to be rearranged, so 1001 and 101110 are abelian squares (of orders 2 and 3, respectively). The order of an abelian square is half its length.
Evdokimov proves that a(1) <= 25. Entringer, Jackson, & Schatz prove that a(3) = 19.
|
|
REFERENCES
|
A. A. Evdokimov, Strongly asymmetric sequence generated by a finite number of symbols, Dokl. Akad. Nauk SSSR, Tom 179 (1968), pp. 1268-1271, Also in: Soviet Math. Dokl., 9 (1968) 536-539. Cited in Brown 1971.
|
|
LINKS
|
|
|
FORMULA
|
Entringer, Jackson, & Schatz prove that a(n) <= n^2 + 6n. Grant proves that a(n) >= n^2/2 . This means that lim inf a(n)/n^2 >= 1/2 and lim sup a(n)/n^2 <= 1.
|
|
EXAMPLE
|
Without loss of generality the first digit of a binary string can be assumed to be 1. If the next were also a 1 the string would be a square, 1 followed by 1, and so let the second digit be 0. If the third digit were a 0 the string would contain the square 00, so let the third digit be 1. But 1010 and 1011 both contain squares (10 and 1, respectively), and so a(1) = 4.
|
|
PROG
|
(PARI) hasAbelianSquare(v, minLen)=for(len=minLen, #v\2, for(i=1, #v+1-2*len, if(sum(j=i, i+len-1, v[j])==sum(j=i+len, i+2*len-1, v[j]), return(1)))); 0
allHaveAbelianSquares(n, k)=my(v=vector(k), t); for(i=2^(k-1), 2^k-1, t=valuation(i, 2)+1; v[t]=1-v[t]; if(!hasAbelianSquare(v, n), return(0))); 1
a(n, startSearch=2*n)=for(k=startSearch, n^2+6*n, if(allHaveAbelianSquares(n, k), return(k)))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|