This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A237695 Maximum length of a +/- 1 sequence of discrepancy n. 1
 0, 11, 1160 (list; graph; refs; listen; history; text; internal format)
 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 P. Erdős, Some unsolved problems, Michigan Math. J. 4 (1957), pp. 291-300. Timothy Gowers, Erdős and Arithmetic Progressions, arXiv:1509.03421 [math.CO], Sep 11 2015 Timothy Gowers et al., Polymath5: The Erdős discrepancy problem, 2010-2014+. James Grime, New Wikipedia sized proof explained with a puzzle (2014) Erica Klarreich, A magical answer to an 80-year-old puzzle, Quanta Magazine, October 2015. Boris Konev and Alexei Lisitsa, A SAT attack on the Erdős Discrepancy Conjecture, arXiv:1402.2184 [cs.DM], 2014. Boris Konev and Alexei Lisitsa, Computer-aided proof of Erdős discrepancy properties, Artificial Intelligence 224 (2015), pp. 103-118. Terence Tao, The Erdős Discrepancy Problem, arXiv:1509.05363 [math.CO], Sep 2015. FORMULA If a(n) exists for some positive n, then a(n) >= 9^(n-1). - Charles R Greathouse IV, Mar 03 2014 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 Sequence in context: A177068 A222827 A067105 * A180581 A233012 A019524 Adjacent sequences:  A237692 A237693 A237694 * A237696 A237697 A237698 KEYWORD nonn,bref,hard,more,nice AUTHOR Charles R Greathouse IV, Feb 11 2014 STATUS approved

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

Last modified October 21 08:47 EDT 2019. Contains 328292 sequences. (Running on oeis4.)