Compute the maximum number of runs possible for as large a string as possible [This question is a follow up to Compute the runs of a string ]


  A period p of a string w is any positive integer p such that w[i]=w[i+p]
  whenever both sides of this equation are defined. Let per(w) denote
  the size of the smallest period of w . We say that a string w is
  periodic iff per(w) &lt;= |w|/2.  


So informally a periodic string is just a string that is made up from another string repeated at least once.  The only complication is that at the end of the string we don't require a full copy of the repeated string as long as it is repeated in its entirety at least once.

For, example consider the string x = abcab. per(abcab) = 3 as x[1] = x[1+3] = a, x[2]=x[2+3] = b and there is no smaller period. The string abcab is therefore not periodic.  However, the string ababa is periodic as per(ababa) = 2.

As more examples, abcabca, ababababa and abcabcabc are also periodic.

For those who like regexes, this one detects if a string is periodic or not:

\b(\w*)(\w+\1)\2+\b


The task is to find all maximal periodic substrings in a longer string.  These are sometimes called runs in the literature.


  A substring w is a maximal periodic substring (run) if it is periodic and neither w[i-1] = w[i-1+p] nor w[j+1] = w[j+1-p].  Informally, the "run" cannot be contained in a larger "run"
  with the same period.


Because two runs can represent the same string of characters occurring in different places in the overall string, we will represent runs by intervals. Here is the above definition repeated in terms of intervals.


  A run (or maximal periodic substring) in a string T is an interval
  [i...j] with j&gt;=i, such that 
  
  
  T[i...j] is a periodic word with the period p = per(T[i...j]) 
  It is maximal. Formally, neither T[i-1] = T[i-1+p] nor T[j+1] = T[j+1-p].  Informally, the run cannot be contained in a larger run
  with the same period.
  


Denote by RUNS(T) the set of runs in string T.

Examples of runs


The four maximal periodic substrings (runs) in string T = atattatt are T[4,5] = tt, T[7,8] = tt, T[1,4] = atat, T[2,8] = tattatt. 
The string T = aabaabaaaacaacac contains the following 7 maximal periodic substrings (runs):
T[1,2] = aa, T[4,5] = aa, T[7,10] = aaaa, T[12,13] = aa, T[13,16] = acac, T[1,8] = aabaabaa, T[9,15] = aacaaca.
The string T = atatbatatb contains the following three runs. They are:
T[1, 4] = atat, T[6, 9] = atat and  T[1, 10] = atatbatatb.


Here I am using 1-indexing.

The task

Write code so that for each integer n starting at 2, you output the largest numbers of runs contained in any binary string of length n.

Score

Your score is the highest n you reach in 120 seconds such that for all k &lt;= n, no one else has posted a higher correct answer than you.  Clearly if you have all optimum answers then you will get the score for the highest n you post. However, even if your answer is not the optimum, you can still get the score if no one else can beat it.  

Languages and libraries

You can use any available language and libraries you like. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in Linux if at all possible.

Example optima

In the following: n, optimum number of runs, example string.

2 1 00
3 1 000
4 2 0011
5 2 00011
6 3 001001
7 4 0010011
8 5 00110011
9 5 000110011
10 6 0010011001
11 7 00100110011
12 8 001001100100
13 8 0001001100100
14 10 00100110010011
15 10 000100110010011
16 11 0010011001001100
17 12 00100101101001011
18 13 001001100100110011
19 14 0010011001001100100
20 15 00101001011010010100
21 15 000101001011010010100
22 16 0010010100101101001011


What exactly should my code output?

For each n your code should output a single string and the number of runs it contains.

My Machine The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor.  This also means I need to be able to run your code.

Leading answers


49 by Anders Kaseorg in C. Single threaded and run with L = 12 (2GB of RAM).
27 by cdlane in C.
C

This does a recursive search for optimal solutions, heavily pruned using an upper bound on the number of runs that could be finished by the unknown remainder of the string.  The upper bound computation uses a gigantic lookup table whose size is controlled by the constant L (L=11: 0.5 GiB, L=12: 2 GiB, L=13: 8 GiB).

On my laptop, this goes up through n = 50 in 100 seconds; the next line comes at 142 seconds.

#include &lt;stdbool.h&gt;
#include &lt;stdint.h&gt;
#include &lt;stdio.h&gt;
#include &lt;string.h&gt;

#define N (8*sizeof(unsigned long long))
#define L 13
static bool a[N], best_a[N];
static int start[N/2 + 1], best_runs;
static uint8_t end_runs[2 &lt;&lt; 2*L][2], small[N + 1][2 &lt;&lt; 2*L];

static inline unsigned next_state(unsigned state, int b)
{
    state *= 2;
    state += b;
    if (state &gt;= 2 &lt;&lt; 2*L) {
        state &amp;= ~(2 &lt;&lt; 2*L);
        state |= 1 &lt;&lt; 2*L;
    }
    return state;
}

static void search(int n, int i, int runs, unsigned state)
{
    if (i == n) {
        int r = runs;
        unsigned long long m = 0;
        for (int p = n / 2; p &gt; 0; p--) {
            if (i - start[p] &gt;= 2*p &amp;&amp; !(m &amp; 1ULL &lt;&lt; start[p])) {
                m |= 1ULL &lt;&lt; start[p];
                r++;
            }
        }
        if (r &gt; best_runs) {
            best_runs = r;
            memcpy(best_a, a, n*sizeof(a[0]));
        }
    } else {
        a[i] = false;
        do {
            int r = runs, bound = 0, saved = 0, save_p[N/2], save_start[N/2], p, s = next_state(state, a[i]);
            unsigned long long m = 0;
            for (p = n/2; p &gt; i; p--)
                if (p &gt; L)
                    bound += (n - p + 1)/(p + 1);
            for (; p &gt; 0; p--) {
                if (a[i] != a[i - p]) {
                    if (i - start[p] &gt;= 2*p &amp;&amp; !(m &amp; 1ULL &lt;&lt; start[p])) {
                        m |= 1ULL &lt;&lt; start[p];
                        r++;
                    }
                    save_p[saved] = p;
                    save_start[saved] = start[p];
                    saved++;
                    start[p] = i + 1 - p;
                    if (p &gt; L)
                        bound += (n - i)/(p + 1);
                } else {
                    if (p &gt; L)
                        bound += (n - (start[p] + p - 1 &gt; i - p ? start[p] + p - 1 : i - p))/(p + 1);
                }
            }
            bound += small[n - i - 1][s];

            if (r + bound &gt; best_runs)
                search(n, i + 1, r, s);
            while (saved--)
                start[save_p[saved]] = save_start[saved];
        } while ((a[i] = !a[i]));
    }
}

int main()
{
    for (int n = 0; n &lt;= N; n++) {
        if (n &lt;= 2*L) {
            for (unsigned state = 1U &lt;&lt; n; state &lt; 2U &lt;&lt; n; state++) {
                for (int b = 0; b &lt; 2; b++) {
                    int r = 0;
                    unsigned long long m = 0;
                    for (int p = n / 2; p &gt; 0; p--) {
                        if ((b ^ state &gt;&gt; (p - 1)) &amp; 1) {
                            unsigned k = state ^ state &gt;&gt; p;
                            k &amp;= -k;
                            k &lt;&lt;= p;
                            if (!(k &amp; ~(~0U &lt;&lt; n)))
                                k = 1U &lt;&lt; n;
                            if (!((m | ~(~0U &lt;&lt; 2*p)) &amp; k)) {
                                m |= k;
                                r++;
                            }
                        }
                    }
                    end_runs[state][b] = r;
                }
                small[0][state] = end_runs[state][0] + end_runs[state][1];
            }
        }

        for (int l = 2*L &lt; n - 1 ? 2*L : n - 1; l &gt;= 0; l--) {
            for (unsigned state = 1U &lt;&lt; l; state &lt; 2U &lt;&lt; l; state++) {
                int r0 = small[n - l - 1][next_state(state, 0)] + end_runs[state][0],
                    r1 = small[n - l - 1][next_state(state, 1)] + end_runs[state][1];
                small[n - l][state] = r0 &gt; r1 ? r0 : r1;
            }
        }

        if (n &gt;= 2) {
            search(n, 1, 0, 2U);
            printf("%d %d ", n, best_runs);
            for (int i = 0; i &lt; n; i++)
                printf("%d", best_a[i]);
            printf("\n");
            fflush(stdout);
            best_runs--;
        }
    }
    return 0;
}


Output:

$ gcc -mcmodel=medium -O2 runs.c -o runs
$ ./runs
2 1 00
3 1 000
4 2 0011
5 2 00011
6 3 001001
7 4 0010011
8 5 00110011
9 5 000110011
10 6 0010011001
11 7 00100110011
12 8 001001100100
13 8 0001001100100
14 10 00100110010011
15 10 000100110010011
16 11 0010011001001100
17 12 00100101101001011
18 13 001001100100110011
19 14 0010011001001100100
20 15 00101001011010010100
21 15 000101001011010010100
22 16 0010010100101101001011
23 17 00100101001011010010100
24 18 001001100100110110011011
25 19 0010011001000100110010011
26 20 00101001011010010100101101
27 21 001001010010110100101001011
28 22 0010100101101001010010110100
29 23 00101001011010010100101101011
30 24 001011010010110101101001011010
31 25 0010100101101001010010110100101
32 26 00101001011010010100101101001011
33 27 001010010110100101001011010010100
34 27 0001010010110100101001011010010100
35 28 00100101001011010010100101101001011
36 29 001001010010110100101001011010010100
37 30 0010011001001100100010011001001100100
38 30 00010011001001100100010011001001100100
39 31 001001010010110100101001011010010100100
40 32 0010010100101101001010010110100101001011
41 33 00100110010001001100100110010001001100100
42 35 001010010110100101001011010110100101101011
43 35 0001010010110100101001011010110100101101011
44 36 00101001011001010010110100101001011010010100
45 37 001001010010110100101001011010110100101101011
46 38 0010100101101001010010110100101001011010010100
47 39 00101101001010010110100101101001010010110100101
48 40 001010010110100101001011010010110101101001011010
49 41 0010100101101001010010110100101101001010010110100
50 42 00101001011010010100101101001011010110100101101011
51 43 001010010110100101001011010110100101001011010010100


Here are all optimal sequences for n ≤ 64 (not just the lexicographically first), generated by a modified version of this program and many hours of computation.

A remarkable nearly-optimal sequence

The prefixes of the infinite fractal sequence

1010010110100101001011010010110100101001011010010100101…


that is invariant under the transformation 101 ↦ 10100, 00 ↦ 101:

  101   00  101   101   00  101   00  101   101   00  101   101   00  …
= 10100 101 10100 10100 101 10100 101 10100 10100 101 10100 10100 101 …


seem to have very nearly optimal numbers of runs—always within 2 of optimal for n ≤ 64. The number of runs in the first n characters divided by n approaches (13 − 5√5)/2 ≈ 0.90983. But it turns out this is not the optimal ratio—see comments.