Output this binary sequence of length 1160:


The sequence

This finite sequence is tightly structured in a way that I hope lends to unique methods for compression. It arises from the Erdős discrepancy problem, which was featured in a previous challenge.

Treating the terms as +1 and -1, this is a maximal-length sequence of discrepancy 2, which means that:

For every positive step size d, if you take every d'th term (starting with the dth term), the running sum of the resulting sequence remains between -2 and 2 inclusive.

If you think of each + to mean a step right and - to mean a step left, this means that the walk of every dth instruction never travels more than 2 steps away from the start position.

For example, for d=3, taking every 3rd term gives the sequence +-++--+--+-..., whose running sums are [1,0,1,2,1,0,1,0,-1,0,1,...], which never hit -3 or 3.

  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^
  +  -  +  +  -  -  +  -  -  +  -
   1  0  1  2  1  0  1  0 -1  0  -1  ...

This sequence was found in 2014 via a computer search. See this paper, where the sequence is reproduced in Appendix B. The search proves that 1160 is the maximum length of a discrepancy-2 sequence, though there is more than one sequence of that length. The Erdős discrepancy problem, proven in 2015, says that any such sequence must have finite length for any maximum discrepancy c in place of 2.

Time requirement

Your code should finish within 5 seconds. This is to limit brute-forcing.

Output format

You can use any two fixed distinct characters or values for + and - in any list-like or string-like format. The format should be one where the 1160 bit-values can be directly read off, not for example encoded as a number via its binary representation or a string via character values. For string output, a trailing newline is allowed.


var QUESTION_ID=122304,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/122304/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

  • \$\begingroup\$ most common substrings of length 1-16 if anyone wants to know \$\endgroup\$ – ASCII-only May 24 '17 at 4:07
  • \$\begingroup\$ I feel like it will be very hard to beat compression... \$\endgroup\$ – Esolanging Fruit May 24 '17 at 4:30

17 Answers 17


Jelly, 149 bytes


There is some pattern, for example only 81 of the 256 length 8 binary strings are present if one chops the sequence into eights, but I have not (at least yet) noticed any way to utilise any to reduce byte count from this straight forward base 250 compression converted to a binary list.

Try it online! (the footer formats the binary list to a string for easier direct comparison).


Python 2, 269 259 256 247 245 243 bytes

while c:t=sum(sum(r[::-k])/3for k in range(1,264)if len(r)%k<1);r[-1:]=cmp(0,t)or c%2*2-1,1;c>>=t==0
print r

Try it online!


JavaScript (ES6), 263 253 252 bytes

I tried to use as less payload data as possible. Sadly -- but not surprisingly -- this requires quite a lot of decompression code.


  • payload data: 75 bytes, encoded as a 100-character Base64 string
  • code: 163 153 152 bytes

Below is a formatted version without the data. The raw code is in the demo snippet.

f = (a = Array(264).fill(n = p = 0)) =>
  n++ < 1160 ?
      p += !a.some((v, i) =>
        n % i | v * v - 4 ?
          r = v / 2,
        r = atob`...`.charCodeAt(p / 8) >> p % 8 & 1 || -1
      r + 1
    ] +
    f(a.map((v, i) => n % i ? v : v - r))


We keep track of the running sums a[i] of every i-th terms. Each time one these sums hit the lower bound -2, we know that the next term must be a +. The same logic applies to the upper bound. This is helpful up to i = 264 and doesn't save any extra byte beyond that.

This leaves us with 599 terms that cannot be guessed. We store them as ⌈599 / 8⌉ = 75 bytes, encoded in a 100-character Base64 string.



o.innerHTML = f()
<pre id=o style="white-space:pre-wrap;word-wrap:break-word">


Jelly, 110 109 107 bytes


This takes too long on TIO, but it finishes in under 3 seconds on my desktop computer.

Try it online!


Jelly, 135 133 130 129 105 104 bytes


Based on the previous elements of the sequence, the algorithm makes an educated guess what the next element could be. This works for all but 99 elements, whose indices are hardcoded so the corresponding elements can be swapped.

Try it online!


MATL, 224 bytes

862:o'$Te]BQHoHxkw!-CEjv(j=zGp.8_C{\?wkH{t&%W.:ja#7=+>"/,=0wDJ+"2BREtgh9_2I%1>+99T3kPrknzlJ}&8kUR(S!pX]C]05u{"6MHA7"gg(M6\5Vp.k.18Y(c~m&wroTrN)sf" |>\,Lg80C:nUez|l;<h~m(%]4xx6?`=qGtZ):d"*"@~1M.T}jJ)Bl7>Ns >9$8R1MlkG'F3:qZaY"

The ouput is of the form 1 0 0 1 0 ..., where 1 corresponds to '-' and 0 corresponds to '+'.

Try it online!


The sequence has been run-length encoded. All 720 runs have lengths 1, 2, 3 or 4, with 3 or 4 being less common. So each 3 has been replaced by 2, 0, 1 (a run of 2, then a run of 0 of the other symbol, then a run of 1 again) and similarly each 4 has been replaced by 2, 0, 2. This gives a ternary array of length 862.

This array is converted to base-94 encoding, and is the long string shown in the code ('$Te...kG'). Base 94 encoding uses all 95 printable ASCII chars except for the single quote (which would have to be escaped).

The code converts that string from base 94 to base 3, and uses the result to run-length decode the symbols [1 0 1 0 ... 0] (array of length 862).


Jelly, 95 bytes

“qạʂṅs⁽fØʋZ%BÞġı½.m0&u⁺TsƝȧAuỴż⁶3uÞ$+ȷ@4Ṣ’BḤC©µmLÆD$§SṠȯ®ṪNLḟ“⁶ .£µ+£gÐ9Ц.ñ×µ¥¤®‘ÄḤ¤ɗ}¡ṭø⁽¡ɠ¡Ḋ

A middle point between my two previous approaches.

The code attempts to guess 842 elements of the sequence and hardcodes the remaining 318 ones. 19 of the guesses are incorrect and have to be reverted via a list of hardcoded indices.

Try it online!

How it works


This is a bijective base 250 literal that uses Jelly's code page for digits and encodes the integer \$\scriptsize 380009100940380065412452185545474826295694594854898450166594167299196720639075810827320738450934\$, which © stores in the register.


B converts the integer to binary, unhalves/doubles the resulting bits, then C subtracts the results from \$1\$. The result is a list of 318 copies of \$\pm1\$.

µmLÆD$§SṠȯ®ṪNLḟ“⁶ .£µ+£gÐ9Ц.ñ×µ¥¤®‘ÄḤ¤ɗ}¡ṭ

This monadic chain takes a prefix of the desired output (with a prepended \$0\$) and appends the next element of the output. The chain works as follows:

mLÆD$§SṠȯ®ṪNLḟ“⁶ .£µ+£gÐ9Ц.ñ×µ¥¤®‘ÄḤ¤ɗ}¡ṭ  Monadic chain. Arument: A (array)

 LÆÐ$                                       Compute all divisors of the length of A.
m                                           For each divisor d, generate the subarray
                                            of each d-th element.
     §                                      Take the sum of each subarray.
      S                                     Take the sum of the sums.
       Ṡ                                    Take the sign of the sum.
        ȯ®                                  If the result is 0, replace it with the
                                            array in the register.
          Ṫ                                 Tail; pop and yield the last element,
                                            modifying the register for a zero sum.
                                            This is a no-op for a non-zero sum.
              “⁶ .£µ+£gÐ9Ц.ñ×µ¥¤®‘ÄḤ¤      Yield all indices of incorrect guesses.
           NLḟ                        ɗ¡    If the length of A doesn't appear among
                                            the indices, negate the result.
                                        ṭ   Append the result to A.

This niladic chain resets the return value to \$0\$, calls the monadic link from above 1160 times (⁽¡ɠ encodes the integer \$1160\$), then removes the first element (\$0\$) with .

  • \$\begingroup\$ Seems like arithmetic encoding would be simpler than manually changing some entries; have you tried that or is Jelly unsuited for it? \$\endgroup\$ – lirtosiast Nov 29 '18 at 22:58
  • \$\begingroup\$ There are only 19 entries that have to be changed, which are encoded in 23 bytes. I think an arithmetic decoder would be longer than that, at least with the associated data. \$\endgroup\$ – Dennis Nov 29 '18 at 23:03

Charcoal, 150 bytes

”a∧∨~℅¹÷Oμ6fCC⁼∕⁵^;Ÿ‘«·T:∕D_=v§AHŒ,—<Pr¢E!◨±L^|.τ"NO“šþŽ∧<n`bÞE÷β$+Z⟦5⁶⁻.λ‹ζd⧴X>w,⊞?‹⟧⌈⪪-h÷³N“K⁺L¿>ρ@P⟲↘3νηKx÷?>™Ž¿•:8V¦£œεG↧x℅7¶	NRü"m”⟦)&¶bE“Yv”

Try it online!

Makes use of Charcoal's builtin string compression. Uses . for - and ! for +.


CJam, 153 bytes


Uses 1 for -, and 0 for +.

Contains unprintables. Try it online!

This is pretty simple. Converts a long sequence from base 256 to base 2.


Python 2, 364 250 bytes

Thanks to Jonathan Allan for saving 114 bytes.

print bin(int('28x0lphxjx8ze4uuhtdzo0oebr25amtmuxm62cbit0ibdwjm2sf50clh2ejq0a73ndseo5tove8uqca6nf66bo4abbkg867woh2b435at0o3pddvqmsqp29b6as5bd4eo28xgwkkj607gp66icba1q4n9fc13dltp45j340mpzbc56wsrbb3oejnczsbzfgh82xdi8aku8m4wlmwuxkgy4yaew7pu4p1g',36))[2:]

Try it online!


C#, 385 bytes


  • Input none
  • Output String The pretended result.


()=>{var s="i´\u009aM6³E¤òi°ÚÍF\u009bM\"Ói6\u009au\u000e\u0093\u008d¤åK´\u009am&qѦRé´Òi\u0096¥i¤Õ«\u0014ò5¦\u0093O\"òm4\u009am4\u009bC¦qibÚLô\u0093ÉÆÓ)6\u0092í&[I6\u009ci±ÆÃ\u0096\u0093M¬Ì;0ÜÇ\nÛPæ\u009bI4Úe*ñY*×).\\i6cY¢ÒÍ4ºer\u009bIbÖiÐËY¦³E§\nÍ6ÒO\u0018­rÊV;";var o="";foreach(var c in s)foreach(var b in Convert.ToString(c,2).PadLeft(8,'0'))o+=(char)(43+(49-(int)b)*2);return o;};


() => {
    var s = "i´\u009aM6³E¤òi°ÚÍF\u009bM\"Ói6\u009au\u000e\u0093\u008d¤åK´\u009am&qѦRé´Òi\u0096¥i¤Õ«\u0014ò5¦\u0093O\"òm4\u009am4\u009bC¦qibÚLô\u0093ÉÆÓ)6\u0092í&[I6\u009ci±ÆÃ\u0096\u0093M¬Ì;0ÜÇ\nÛPæ\u009bI4Úe*ñY*×).\\i6cY¢ÒÍ4ºer\u009bIbÖiÐËY¦³E§\nÍ6ÒO\u0018­rÊV;";
    var o = "";

    foreach( var c in s )
        foreach( var b in Convert.ToString( c, 2 ).PadLeft( 8, '0' ) )
            o += (char) ( 43 + ( 49 - (int) b ) * 2 );

    return o;

Full code

using System;

namespace Namespace {
   class Program {
      static void Main( String[] args ) {
        Func<String> f = () => {
            var s = "i´\u009aM6³E¤òi°ÚÍF\u009bM\"Ói6\u009au\u000e\u0093\u008d¤åK´\u009am&qѦRé´Òi\u0096¥i¤Õ«\u0014ò5¦\u0093O\"òm4\u009am4\u009bC¦qibÚLô\u0093ÉÆÓ)6\u0092í&[I6\u009ci±ÆÃ\u0096\u0093M¬Ì;0ÜÇ\nÛPæ\u009bI4Úe*ñY*×).\\i6cY¢ÒÍ4ºer\u009bIbÖiÐËY¦³E§\nÍ6ÒO\u0018­rÊV;";
            var o = "";

            foreach( var c in s )
                foreach( var b in Convert.ToString( c, 2 ).PadLeft( 8, '0' ) )
                    o += (char) ( 43 + ( 49 - (int) b ) * 2 );

            return o;

        Console.WriteLine( $" Input: <none>\nOutput: {f()}\n" );



  • v1.0 - 385 bytes - Initial solution.


  • None

05AB1E, 149 bytes

pт6½÷Ü;вVåΔĀÈ₄¤Ü³Aʒм5[¦PŠÅøœ^‚₆賦ìóV“LÛ'ßq;αÎΩªî»(2∍©däf×5 V5Ú”gÜ/\^(Ã∊Ƶ!3šÍ3°(§A΄ǝ₂È₅ç£6óàÖCsa*zƒÚ¥Î\ªD¹,n∊ðˆ.ëçPαǝƒ.É∍¯ü₂³Λ‘g∍Θþ“‚œΔи‹•b

Super boring. Just a compressed number. Uses 1 for - and 0 for +.

Try it online!


PHP, 276 Bytes


Try it online!


Ruby, 245 bytes


Output 0 for + and 1 for -.

Try it online!


Perl, 164 bytes

print unpack'b*','-Y²lÍ¢%O


00000000: 7072 696e 7420 756e 7061 636b 2762 2a27  print unpack'b*'
00000010: 2c27 962d 59b2 6ccd a225 4f96 0d5b b362  ,'.-Y.l..%O..[.b
00000020: d9b2 44cb 966c 59ae 70c9 b125 a7d2 2d59  ..D..lY.p..%..-Y
00000030: b664 8e8b 654a 972d 4b96 69a5 9625 abd5  .d..eJ.-K.i..%..
00000040: 284f ac65 c9f2 444f b62c 59b6 2cd9 c265  (O.e..DO.,Y.,..e
00000050: 8e96 465b 322f c993 63cb 946c 49b7 64da  ..F[2/..c..lI.d.
00000060: 926c 3996 8d63 c369 c9b2 3533 dc0c 3be3  .l9..c.i..53..;.
00000070: 50db 0a67 d992 2c5b a654 8f9a 54eb 9474  P..g..,[.T..T..t
00000080: 3a96 6cc6 9a45 4bb3 2c5d a64e d992 466b  :.l..EK.,].N..Fk
00000090: 960b d39a 65cd a2e5 50b3 6c4b f218 b54e  ....e...P.lK...N
000000a0: 536a dc27                                Sj.'

The obvious, boring solution: just put all the bits in a binary string, 8 bits per byte. Uses 0 for - and 1 for +. I’ll try to golf this some more.


Python 3, 236 232 bytes

Thanks to Mego for saving 4 bytes


Try it online!

Uses the CP-437 encoding. Thanks to Dennis for pointing out an error.

  • \$\begingroup\$ 437 is an alias for cp437, so you can shave off 4 bytes by getting rid of the cp bits both times they occur. \$\endgroup\$ – Mego May 28 '17 at 9:33

Retina, 333 bytes


Try it online!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.