|
|
A237695
|
|
Maximum length of a +- 1 sequence of discrepancy n.
|
|
2
|
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
There is a sequence s_1, s_2, ..., s_a(n) with all terms either 1 or -1 such that abs(s_k + s_2k + ... + s_mk) <= n, but no such sequence with more terms.
The Erdős Discrepancy Conjecture states that a(n) is finite for all n.
Konev & Lisitsa find a(2) = 1160 and a(3) >= 13000. The Polymath5 project had earlier determined that a(2) >= 1124.
Terence Tao solved the Erdős Discrepancy Problem showing that "for any sequence f: N -> {-1,+1} taking values in {-1,+1}, the discrepancy sup_{n,d in N} |Sum_{j=1..n} f(jd)| of f is infinite." (From the abstract of Tao's paper, see the link.) - Peter Luschny, Sep 18 2015
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
Writing + for 1 and - for -1, the maximal sequences of maximal discrepancy 1 are +--+-++--+-, +--+-++--++, and their inverses.
|
|
PROG
|
(PARI) mk(n)=apply(k->if(k, 1, -1), binary(n))
ok(n, mx)=my(v=mk(n)); for(k=1, #v\2, my(s); forstep(i=k, #v, k, s+=v[i]; if(abs(s)>mx, return(0)))); 1
a(n)=if(n==0, return(0)); my(k=2^10); while(1, for(i=k+1, 2*k, if(ok(i, n), k=i; next(2))); return(#binary(k)))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,bref,hard,more,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|