Maximal discrepancy-2 sequence with minimal entropy

Question

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.

Answer 1

C (gcc), 472 bytes

a[]={-1384986026,919752472,1168575181,-883317069,1658218960,1702009673,-758303558,912480674,690904169,-245814569,886727978,1357290313,-590935333,-1395901648,-1013542067,-1670794810,643516726,691442413,-1815492909,1658473716,1134981481,-1704119141,586313012,900109135,-710208270,-1767544412,-374025623,1909565010,-1264947930,-1918573237,-1703604589,584280374,-851010739,-227954470,917718436,1773443661};f(i){for(i=1152;i--;)putchar(a[i/32]>>i%32&1?43:45);puts("--+++-++");}

-702 bytes thanks to ceilingcat!

Try it online!

C (gcc), 472 bytes

a[]={-1384986026,919752472,1168575181,-883317069,1658218960,1702009673,-758303558,912480674,690904169,-245814569,886727978,1357290313,-590935333,-1395901648,-1013542067,-1670794810,643516726,691442413,-1815492909,1658473716,1134981481,-1704119141,586313012,900109135,-710208270,-1767544412,-374025623,1909565010,-1264947930,-1918573237,-1703604589,584280374,-851010739,-227954470,917718436,1773443661};f(i){for(i=1152;i--;)putchar(a[i/32]>>i%32&1?45:43);puts("--+++-++");}

Negated form of the above.

Try it online!

C (gcc), 1148 bytes, non-competing

#include <limits.h>
#include <stdint.h>
#include <stdio.h>

#define DISCREPANCY 2
#define NTERMS 1160

#define NBITS(x) (sizeof(x) * CHAR_BIT)

static int terms[NTERMS];

/* non-branching abs */
static inline int abs_(int x)
{
    return (x ^ (x >> (NBITS(x) - 1))) - (x >> (NBITS(x) - 1));
}

/* generate and print terms */
int main(void)
{
    register int result = 0, iter, incr;

    for(iter = 0; iter < NTERMS; iter++)
        terms[iter] = 1;

    for(incr = NTERMS; incr > 0; incr--)
    {
        result = 0;

        for(iter = incr - 1; iter < NTERMS; iter += incr)
        {
            result += terms[iter];
            if(abs_(result) > DISCREPANCY)
            {
                /* undo change */
                /* result -= terms[iter]; */
                /* change term to fit requirements */
                terms[iter] = -terms[iter];
                /* do correct change */
                result += 2 * terms[iter];
            }
        }
    }

    for(iter = 0; iter < NTERMS; iter++)
    {
        if(iter == NTERMS-1)
            printf("%d\n", terms[iter]);
        else
            printf("%d, ", terms[iter]);
    }
}

This is my half-brute-force half-calculating solution but it breaks when you check every third term. I hope to improve it to the point where it generates a correct solution. Replace the 1 with -1 on line 24 to negate the sequence.

Try it online!