# Compress a maximal discrepancy-2 sequence

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.

• most common substrings of length 1-16 if anyone wants to know May 24 '17 at 4:07
• I feel like it will be very hard to beat compression... May 24 '17 at 4:30

# Jelly, 149 bytes

“×GOẈ*m¬¿3d{ẋạ⁻@Ɓ]ZĊỵINBƬḊṿẊ*N¹Ẹ÷ƲẋɼoṬḳ£®⁾ƙŒọ¡[P1&ạ€ẊʠNỌXḢṖėÐß⁹Ụṗ¬⁹E#ụḷḌṁżżR=ƊÑ³ıɲ-ṭỌṾɲẎĿỴ⁶€ḋtɦÐ\ỵƒ⁾ƒụṫṡĊKpƭẏkaṪ,Ẋȧ⁻ḅMɓ%YḷsƲƭl¤æĊbṬ9D6ẎƘẓ^Œ⁷Ɲḷḷ€ḟ1g’B

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, 269259256247245 243 bytes

r=[1]
c=int('bmqnh8j8rdo4mirjos6uxbfthu8t39pjy6up43axryzwbwcu5d528nsakitjwqbo6dnnozy0oybhk6jduaoc53lqkzdb04opj5t50a24w9he5y7qbgd2',36)
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), 263253 252 bytes

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

Breakdown:

• 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 ?
0
:
r = v / 2,
r = atob....charCodeAt(p / 8) >> p % 8 & 1 || -1
),
r + 1
] +
f(a.map((v, i) => n % i ? v : v - r))
:
''

### How?

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.

### Demo

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

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

# Jelly, 110109 107 bytes

;1mS€:3o/Nȯ®Ṫṭḷ
“ĖṄẋ{Xṛ-İIṗ®6⁼Ḟ2a⁻!Ċẉȥ+¡Ƒ¥mvrẓsṘ×⁴ç&$nỴỤ)M7?ẊẎḅ=ṠƈTṙḌȥụẋXḌ⁵Ḣ⁺ḲL÷æTƥĿv€%ḟ¢®!Ė’BḤ’©ṛ⁽¡ɠÆD€Nç/ This takes too long on TIO, but it finishes in under 3 seconds on my desktop computer. Try it online! # Jelly, 135133130129105 104 bytes 42“I=İėZP*ðEḄẈṆ'mBƝėŻƝ6®Ṇɼḥ[bȦėṡV£(6ṘɱX)Ṅẹ6~K7°ȤÄỴ¥ƝÇ5prḳġŻ£ƭṗṄFṾḃ{©@ɼ’ḃÄċL L+Ø.ÆDm@NÇ¡§§No¥/Ṡo-ṭ Ç⁽¡ɠ¡Ḋ 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! ### Explanation 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

“qạʂṅs⁽fØʋZ%BÞġı½.m0&u⁺TsƝȧAuỴż⁶3uÞ$+ȷ@4Ṣ’ 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ḤC© 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 .

• Seems like arithmetic encoding would be simpler than manually changing some entries; have you tried that or is Jelly unsuited for it? Nov 29 '18 at 22:58
• 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. Nov 29 '18 at 23:03

# Charcoal, 150 bytes

”a∧∨~℅¹÷Ｏμ6fＣC⁼∕⁵^;Ÿ‘«·T:∕Ｄ_=v§AＨŒ,—<Ｐr¢E!◨±Ｌ^|.τ"ＮO“šþŽ∧<nbÞＥ÷β$+Ｚ⟦5⁶⁻.λ‹ζd⧴X>w,⊞?‹⟧⌈⪪-h÷³N“Ｋ⁺L¿>ρ@Ｐ⟲↘3νηKx÷?>™Ž¿•:8Ｖ¦£œεＧ↧x℅7¶ NＲü"m”⟦)&¶bＥ“Ｙv” Try it online! Makes use of Charcoal's builtin string compression. Uses . for - and ! for +. ## CJam, 153 bytes "Ke²ÉLº[ O%2¹d²Ý,Éeñlr[´KeÙ.Y­K-iZ[*Të ÊYl°Ý ËeËd¼Y%³l69,ÖÉmÙ¤¶ÉcN9<il²S3ÄÏ#8õ$¯d¶Ë%Õ¦Õ(ÖÑ£É¦]-2ËEd¶)/4¦YLºXõ2É-°çR5©Ä"256b2b

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 3, 236 232 bytes

Thanks to Mego for saving 4 bytes

#coding:437

}
}
}

### Releases

• v1.0 - 385 bytes - Initial solution.

• None

# 05AB1E, 149 bytes

•19GÈRÕŸ

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

Try it online!

# PHP, 276 Bytes

<?=gzinflate(base64_decode("dVJRFgMgCDoQj/tfb2+boqj9VJohQgQI8rv+D1yHuIIytGLsYh6vwAlYIMS62mVCiWMm56vfHiGOuTwjiMHQEC7OVlkNzzK0LZFTN8l0gavGdX4wOfJDsZpXZS0csig0l13wEsoRlvKzhYHMv+F9MnxaCXHWrC2Kx4UqQ8o4qmgNcsjbzA5lZG7LE6LdNMlt2sRKFpNhk/sL59N6DSMKp4No7vP2QcP0c2XWb6nPblqYfJBfHw=="));

Try it online!

# Ruby, 245 bytes

puts"%b"%"28x0lphxjx8ze4uuhtdzo0oebr25amtmuxm62cbit0ibdwjm2sf50clh2ejq0a73ndseo5tove8uqca6nf66bo4abbkg867woh2b435at0o3pddvqmsqp29b6as5bd4eo28xgwkkj607gp66icba1q4n9fc13dltp45j340mpzbc56wsrbb3oejnczsbzfgh82xdi8aku8m4wlmwuxkgy4yaew7pu4p1g".to_i(36)

Output 0 for + and 1 for -.

Try it online!

## Perl, 164 bytes

print unpack'b*','-Y²lÍ¢%O
[³bÙ²DËlY®pÉ±%§Ò-Y¶deJ-Ki¥%«Õ(O¬eÉòDO¶,Y¶,ÙÂeF[2/ÉcËlI·dÚl9cÃiÉ²53Ü;ãPÛ
gÙ,[¦TTët:lÆEK³,]¦NÙFkÓeÍ¢åP³lKòµNSjÜ'

Hexdump:

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.

R
GF
Q
+C
P
EA
O
CK
N
D-
M
I-A
L
--
K
D+
J
CB
I
A++
H
E+
G
AB
F
E
C+
D
B+
C
-B
B
-+
A
-++-+-

Try it online!