23
5
Background
As noted in the PPCG challenge Compress a maximal discrepancy-2 sequence – which inspired this challenge – the authors of the paper Computer-Aided Proof of Erdős Discrepancy Properties found a maximal discrepancy-2 sequence, namely
-1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, -1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, 1, -1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, -1, -1, -1, 1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, 1, -1, 1, -1, -1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, -1, -1, 1, -1, 1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, 1, -1, -1, 1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, 1, -1, 1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, -1, 1, -1, 1, -1, -1, 1, 1, 1, 1, -1, -1, 1, -1, -1, -1, 1, 1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, -1, -1, 1, -1, -1, -1, 1, -1, 1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, -1, -1, 1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, -1, 1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, -1, -1, 1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, -1, -1, -1, 1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, -1, -1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, -1, -1, -1, -1, 1, 1, -1, 1, 1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, -1, -1, -1, 1, -1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, -1, 1, -1, -1, -1, -1, 1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, -1, -1, 1, -1, 1, -1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1, -1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, -1, 1, -1, -1, 1, -1, -1, 1, -1, 1, 1, 1, -1, -1, 1, -1, 1, 1, 1, -1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, 1, -1, -1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, -1, -1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, -1, -1, 1, 1, 1, 1, -1, -1, -1, 1, 1, -1, -1, -1, 1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, -1, 1, -1, -1, 1, -1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, 1
However, this is not the the only discrepancy-2 sequence of the length 1160; apart from the obvious variation of negating every term of the sequence, the are many valid variations that involve negating a pair of terms, and possibly entirely unrelated approaches that also lead to maximal sequences. The papers's authors made several design decisions that sped up their algorithm, but would a different set of decisions lead to a more compressible sequence? Let's find out!
Definitions
Let \$k\$ and \$n\$ be positive integers. A finite sequence \$x_1, \dots, x_n\$ over \$\{-1, 1\}\$ is of discrepancy \$d\$ if
$$ \max_{1\leq k\leq m\leq n} \left| \sum_{1\leq jk\leq m} x_{jk} \right| \leq d $$
In other words, the partial sums of the subsequences resulting of taking every \$k\$th term of \$x\$ all lie in the interval \$[-d, d]\$.
The sequence provided by the authors is of discrepancy 2, as can be verified programmatically. For the first three values of \$k\$, we get the following subsequences and partial sums.
k = 1: -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, ...
(sums) -1, 0, 1, 0, 1, 0, -1, 0, 1, 0, 1, 2, 1, 2, 1, 0, 1, 0, ...
k = 2: 1, -1, -1, 1, -1, 1, 1, -1, -1, ...
(sums) 1, 0, -1, 0, -1, 0, 1, 0, -1, ...
k = 3: 1, -1, 1, 1, -1, -1, ...
(sums) 1, 0, 1, 2, 1, 0, ...
Later terms of the sequences of partial sums never reach -3 or 3.
In contrast, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1 is not a discrepancy-2 sequence.
k = 1: 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1
(sums) 1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0
k = 2: -1, 1, -1, 1, -1, 1
(sums) -1, 0, -1, 0, -1, 0
k = 3: -1, -1, 1, 1
(sums) -1, -2, -1, 0
k = 4: 1, 1, 1
(sums) 1, 2, 3
Task
Write a full program or a function that takes no input, prints or returns a single discrepancy-2 sequence with 1160 terms, and abides to the following rules.
You can use any kind of iterable (arrays, strings, etc.) that consists of exactly two different symbols: one representing -1 and one representing 1.
Your output must be consistent, i.e., every time your code is run, it must output the same sequence.
You must include the output of your program in your answer.
Hardcoding your output sequence is allowed.
To prevent trivial brute-force solutions, your code must finish in under a minute. For borderline-compliant solutions, I'll determine the official run time on my own machine (Intel Core i7-3770, 16 GiB RAM, openSUSE 13.2) or a sufficiently similar one if I cannot test your code on mine.
Any built-in that is itself a valid submission to this challenge or a variation that takes the discrepancy as input (e.g.,
FindMaximalDiscrepancySequence
) may not be in your answer. All other built-ins – including built-ins that calculate the discrepancy of a sequence – are allowed.
While finding a suitable sequence is a big part of the task, only your implementation contributes to your score. In other words, this is code-golf, and may the shortest code in bytes win!
Validation
You can use this Python script to verify the output of your submission. It expects a string of comma-separated -1's and 1's.
4I don't know if other people will understand it but defining discrepancy in less mathy notation would be good. – Christopher – 2017-05-28T19:39:19.533
10Everything after the image is a less mathy explanation of discrepancy. Which part is unclear? – Dennis – 2017-05-28T19:47:06.147
"the partial sums of the subsequences resulting of taking every kth term of x all lie in the interval [-d, d]. Is the hard part to understand, I am getting it slowly but other words may work better – Christopher – 2017-05-28T19:52:19.833
I am trying to figure out a way to get it easier for others to understand, It is a good challenge otherwise – Christopher – 2017-05-28T19:52:50.633
I think you forgot one rule: it may not be the sequence displayed at the top or it's negated form? What stops me from simply outputting the sequence at the top and post it at as answer right now? – Kevin Cruijssen – 2017-09-20T09:23:09.170
@KevinCruijssen Nothing. There are many more sequences that are trivial variations (only changing a couple of elements) of the one at the top. The idea is to find a more compressible sequence though, and if/when someone does, I expect it to outgolf answers using the sequence at the top by quite a bit. – Dennis – 2017-09-20T16:15:12.430
I'm really interested in this topic. Just now, I had completed brute-forced the sequence of 500 integers and found the mentioned one has a realtively low entropy. – Keyu Gan – 2017-10-17T04:02:23.287