23
\$\begingroup\$

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 , 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.

\$\endgroup\$
  • 4
    \$\begingroup\$ I don't know if other people will understand it but defining discrepancy in less mathy notation would be good. \$\endgroup\$ – Christopher May 28 '17 at 19:39
  • 9
    \$\begingroup\$ Everything after the image is a less mathy explanation of discrepancy. Which part is unclear? \$\endgroup\$ – Dennis May 28 '17 at 19:47
  • \$\begingroup\$ "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 \$\endgroup\$ – Christopher May 28 '17 at 19:52
  • \$\begingroup\$ I am trying to figure out a way to get it easier for others to understand, It is a good challenge otherwise \$\endgroup\$ – Christopher May 28 '17 at 19:52
  • \$\begingroup\$ 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? \$\endgroup\$ – Kevin Cruijssen Sep 20 '17 at 9:23

Your Answer

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

Browse other questions tagged or ask your own question.