Matrix property X revisited (or the Joy of X)
C++, Score 23/12 25/13 27/14 28/14 31/15

Finally a result with ratio > 2:

rows=15,cols=31
1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0 
1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 
1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 
1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 
1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 
0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 
0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 
1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 
0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 
0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 
0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 
1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 
0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 
0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 
1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 


I completely explored 1 to 14 rows. 15 would take too long to completely explore. The results are:

1/1   = 1
2/2   = 1
4/3   = 1.333
5/4   = 1.25
7/5   = 1.4
9/6   = 1.5
12/7  = 1.714
14/8  = 1.75
16/9  = 1.778
18/10 = 1.8
20/11 = 1.818
23/12 = 1.917
25/13 = 1.923
28/14 = 2


The code given below is an older version of the program. The newest version is at https://github.com/thospel/personal-propertyX.

/*
  Compile using something like:
    g++ -Wall -O3 -march=native -fstrict-aliasing -std=c++11 -g propertyX.cpp -lpthread -o propertyX
*/
#include &lt;cstdint&gt;
#include &lt;climits&gt;
#include &lt;ctgmath&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;array&gt;
#include &lt;chrono&gt;
#include &lt;mutex&gt;
#include &lt;atomic&gt;
#include &lt;thread&gt;

using namespace std;

const int ELEMENTS = 2;

using uint    = unsigned int;
using Element = uint64_t;
using Column  = array&lt;Element, ELEMENTS&gt;;
using Set     = vector&lt;Column&gt;;
using Sum     = uint8_t;
using Index   = uint32_t;
using sec = chrono::seconds;

int const PERIOD = 5*60;
int const MAX_ROWS = 54;
int const COL_FACTOR = (MAX_ROWS+1) | 1;                // 55
int const ROW_ZERO   = COL_FACTOR/2;                    // 27
int const ROWS_PER_ELEMENT = CHAR_BIT * sizeof(Element) / log2(COL_FACTOR); //11
Element constexpr ELEMENT_FILL(Element v = ROW_ZERO, int n = ROWS_PER_ELEMENT) {
    return n ? ELEMENT_FILL(v, n-1) * COL_FACTOR + v : 0;
}
Element constexpr POWN(Element v, int n) {
    return n ? POWN(v, n-1)*v : 1;
}
Element const ELEMENT_TOP = POWN(COL_FACTOR, ROWS_PER_ELEMENT -1);
int const MAX_COLS = ROWS_PER_ELEMENT * ELEMENTS;       // 22

atomic&lt;Index&gt; col_next;
atomic&lt;uint&gt;  period;
chrono::steady_clock::time_point start;
mutex period_mutex;

uint ratio_row;
uint ratio_col;
mutex ratio_mutex;

auto const nr_threads = thread::hardware_concurrency();
// auto const nr_threads = 1;

struct State {
    State(uint cols);
    void process(Index i);
    void extend(uint row);
    void print(uint rows);
    Index nr_columns() const { return static_cast&lt;Index&gt;(1) &lt;&lt; cols_; }

    Column last_;
    Element top_;
    int top_offset_;
    uint ratio_row_ = 0;
    uint ratio_col_ = 1;
    uint cols_;
    array&lt;Sum, MAX_ROWS + MAX_COLS -1&gt; side;
    vector&lt;Set&gt; sets;
};

ostream&amp; operator&lt;&lt;(ostream&amp; os, Column const&amp; column) {
    for (int i=0; i&lt;ELEMENTS; ++i) {
        auto v = column[i];
        for (int j=0; j&lt;ROWS_PER_ELEMENT; ++j) {
            auto bit = v / ELEMENT_TOP;
            cout &lt;&lt; " " &lt;&lt; bit;
            v -= bit * ELEMENT_TOP;
            v *= COL_FACTOR;
        }
    }
    return os;
}

State::State(uint cols) : cols_{cols} {
    sets.resize(MAX_ROWS+2);
    for (int i=0; i&lt;2; ++i) {
        sets[i].resize(2);
        for (int j=0; j &lt; ELEMENTS; ++j) {
            sets[i][0][j] =  ELEMENT_FILL();
            sets[i][1][j] =  static_cast&lt;Element&gt;(-1) - ELEMENT_FILL(1);
        }
    }
    top_ = POWN(COL_FACTOR, (cols_-1) % ROWS_PER_ELEMENT);
    top_offset_ = ELEMENTS - 1 - (cols_-1) / ROWS_PER_ELEMENT;
}

void State::print(uint rows) {
    for (auto c=0U; c&lt;cols_;c++) {
        for (auto r=0U; r&lt;rows;r++) {
            cout &lt;&lt; static_cast&lt;int&gt;(side[cols_-c+r-1]) &lt;&lt; " ";
        }
        cout &lt;&lt; "\n";
    }
    cout &lt;&lt; "----------" &lt;&lt; endl;
}

void check(uint cols, uint t) {
    State state(cols);

    Index nr_columns = state.nr_columns();
    while (1) {
        Index col = col_next++;
        if (col &gt;= nr_columns) break;
        state.process(col);

        auto now = chrono::steady_clock::now();
        auto elapsed = chrono::duration_cast&lt;sec&gt;(now-start).count();
        if (elapsed &gt;= period) {
            lock_guard&lt;mutex&gt; lock{period_mutex};
            if (elapsed &gt;= period) {
                cout &lt;&lt; "col=" &lt;&lt; col &lt;&lt; "/" &lt;&lt; nr_columns &lt;&lt; " (" &lt;&lt; 100.*col/nr_columns &lt;&lt; "% " &lt;&lt; elapsed &lt;&lt; " s)" &lt;&lt; endl;
                period = (elapsed/PERIOD+1)*PERIOD;
            }
        }
    }
}

void State::process(Index col) {
    last_.fill(0);
    for (uint i=0; i&lt;cols_; ++i) {
        Element bit = col &gt;&gt; i &amp; 1;
        side[i] = bit;
        Element carry = 0;
        for (int j=0; j&lt;ELEMENTS; ++j) {
            auto c = last_[j] % COL_FACTOR;
            last_[j] = last_[j] / COL_FACTOR + carry * ELEMENT_TOP;
            if (j == top_offset_ &amp;&amp; bit) last_[j] += top_;
            carry = c;
        }
    }
    // cout &lt;&lt; "col=" &lt;&lt; col &lt;&lt; ", value=" &lt;&lt; last_ &lt;&lt; "\n";
    extend(0);
}

void State::extend(uint row) {
    // cout &lt;&lt; "Extend row " &lt;&lt; row &lt;&lt; " " &lt;&lt; static_cast&lt;int&gt;(side[cols_+row-1]) &lt;&lt; "\n";
    if (row &gt;= MAX_ROWS) throw(range_error("row out of range"));

    // Execute subset sum. The new column is added to set {from} giving {to}
    // {sum} is the other set.
    auto const&amp; set_from = sets[row];
    auto const&amp; set_sum  = sets[row + 1];
    auto      &amp; set_to   = sets[row + 2];
    if (set_to.size() == 0) {
        auto size = 3 * set_from.size() - 2;
        set_to.resize(size);
        for (int j=0; j&lt;ELEMENTS; ++j)
            set_to[size-1][j] = static_cast&lt;Element&gt;(-1) - ELEMENT_FILL(1);
    }

    // Merge sort {set_from - last_} , {set_from} and {set_from + last_}
    auto ptr_sum    = &amp;set_sum[1][0];
    auto ptr_low    = &amp;set_from[0][0];
    auto ptr_middle = &amp;set_from[0][0];
    auto ptr_high   = &amp;set_from[0][0];
    Column col_low, col_high;
    for (int j=0; j&lt;ELEMENTS; ++j) {
        col_low   [j] = *ptr_low++  - last_[j];
        col_high  [j] = *ptr_high++ + last_[j];
    }

    auto ptr_end = &amp;set_to[set_to.size()-1][0];
    auto ptr_to  = &amp;set_to[0][0];
    while (ptr_to &lt; ptr_end) {
        for (int j=0; j&lt;ELEMENTS; ++j) {
            if (col_low[j] &lt; ptr_middle[j]) goto LOW;
            if (col_low[j] &gt; ptr_middle[j]) goto MIDDLE;
        }
        // low == middle
        // cout &lt;&lt; "low == middle\n";
        return;

      LOW:
        // cout &lt;&lt; "LOW\n";
        for (int j=0; j&lt;ELEMENTS; ++j) {
            if (col_low[j] &lt; col_high[j]) goto LOW0;
            if (col_low[j] &gt; col_high[j]) goto HIGH0;
        }
        // low == high
        // cout &lt;&lt; "low == high\n";
        return;

      MIDDLE:
        // cout &lt;&lt; "MIDDLE\n";
        for (int j=0; j&lt;ELEMENTS; ++j) {
            if (ptr_middle[j] &lt; col_high[j]) goto MIDDLE0;
            if (ptr_middle[j] &gt; col_high[j]) goto HIGH0;
        }
        // middle == high
        // cout &lt;&lt; "middle == high\n";
        return;

      LOW0:
        // cout &lt;&lt; "LOW0\n";
        for (int j=0; j&lt;ELEMENTS; ++j) {
            *ptr_to++  = col_low[j];
            col_low[j] = *ptr_low++ - last_[j];
        }
        goto SUM;

      MIDDLE0:
        // cout &lt;&lt; "MIDDLE0\n";
        for (int j=0; j&lt;ELEMENTS; ++j)
            *ptr_to++ = *ptr_middle++;
        goto SUM;

      HIGH0:
        // cout &lt;&lt; "HIGH0\n";
        for (int j=0; j&lt;ELEMENTS; ++j) {
            *ptr_to++ = col_high[j];
            col_high[j] = *ptr_high++ + last_[j];
        }
        goto SUM;
      SUM:
        for (int j=-ELEMENTS; j&lt;0; ++j) {
            if (ptr_to[j] &gt; ptr_sum[j]) {
                ptr_sum += ELEMENTS;
                goto SUM;
            }
            if (ptr_to[j] &lt; ptr_sum[j]) goto DONE;
        }
        // sum == to
        for (int j=-ELEMENTS; j&lt;0; ++j)
            if (ptr_to[j] != ELEMENT_FILL()) {
                // sum == to and to != 0
                // cout &lt;&lt; "sum == to\n";
                // cout &lt;&lt; set_sum[(ptr_sum - &amp;set_sum[0][0])/ELEMENTS-1] &lt;&lt; "\n";
                return;
            }
      DONE:;
    }
    // cout &lt;&lt; "Wee\n";
    auto row1 = row+1;
    if (0)
        for (uint i=0; i&lt;row1+2; ++i) {
            cout &lt;&lt; "Set " &lt;&lt; i &lt;&lt; "\n";
            auto&amp; set = sets[i];
            for (auto&amp; column: set)
                cout &lt;&lt; column &lt;&lt; "\n";
        }

    if (row1 * ratio_col_ &gt; ratio_row_ * cols_) {
        ratio_row_ = row1;
        ratio_col_ = cols_;
        lock_guard&lt;mutex&gt; lock{ratio_mutex};

        if (ratio_row_ * ratio_col &gt; ratio_row * ratio_col_) {

            auto now = chrono::steady_clock::now();
            auto elapsed = chrono::duration_cast&lt;sec&gt;(now-start).count();
            cout &lt;&lt; "cols=" &lt;&lt; cols_ &lt;&lt; ",rows=" &lt;&lt; row1 &lt;&lt; " (" &lt;&lt; elapsed &lt;&lt; " s)\n";
            print(row1);
            ratio_row = ratio_row_;
            ratio_col = ratio_col_;
        }
    }

    auto last = last_;

    Element carry = 0;
    for (int j=0; j&lt;ELEMENTS; ++j) {
        auto c = last_[j] % COL_FACTOR;
        last_[j] = last_[j] / COL_FACTOR + carry * ELEMENT_TOP;
        carry = c;
    }

    side[cols_+row] = 0;
    extend(row1);

    last_[top_offset_] += top_;
    side[cols_+row] = 1;
    extend(row1);

    last_ = last;
}

void my_main(int argc, char** argv) {
    if (!col_next.is_lock_free()) cout &lt;&lt; "col_next is not lock free\n";
    if (!period.  is_lock_free()) cout &lt;&lt; "period is not lock free\n";

    int min_col = 2;
    int max_col = MAX_COLS;
    if (argc &gt; 1) {
        min_col = atoi(argv[1]);
        if (min_col &lt; 2)
            throw(range_error("Column must be &gt;= 2"));
        if (min_col &gt; MAX_COLS)
            throw(range_error("Column must be &lt;= " + to_string(MAX_COLS)));
    }
    if (argc &gt; 2) {
        max_col = atoi(argv[2]);
        if (max_col &lt; min_col)
            throw(range_error("Column must be &gt;= " + to_string(min_col)));
        if (max_col &gt; MAX_COLS)
            throw(range_error("Column must be &lt;= " + to_string(MAX_COLS)));
    }

    for (int cols = min_col; cols &lt;= max_col; ++cols) {
        cout &lt;&lt; "Trying " &lt;&lt; cols &lt;&lt; " columns" &lt;&lt; endl;
        ratio_row = 0;
        ratio_col = 1;
        col_next = 0;
        period = PERIOD;
        start = chrono::steady_clock::now();
        vector&lt;thread&gt; threads;
        for (auto t = 1U; t &lt; nr_threads; t++)
            threads.emplace_back(check, cols, t);
        check(cols, 0);
        for (auto&amp; thread: threads)
            thread.join();
    }
}

int main(int argc, char** argv) {
    try {
        my_main(argc, argv);
    } catch(exception&amp; e) {
        cerr &lt;&lt; "Error: " &lt;&lt; e.what() &lt;&lt; endl;
        exit(EXIT_FAILURE);
    }
    exit(EXIT_SUCCESS);
}