# Sources: ten-true-things-computing

Checked again on 23 October 2026 (fix list from the cloud-site review of 22 October). Status key: **opened** = the primary document was opened and the figure appears there; **opened (reference work)** = only a reference work or summary that states the figure was opened, and the page says so; **not opened** = the document could not be opened (what was tried is noted); **computed** = own arithmetic or run; **own reading** = the page's explanation, not a quotation.

| # | Claim on the page | Source | Status |
| --- | --- | --- | --- |
| 1 | 2 July 2019 outage, 27 minutes, CPUs near 100%, caused by a WAF rule's regular expression; several causes listed, among them an engine without complexity guarantees; rule deployed globally | Cloudflare blog, "Details of the Cloudflare outage on July 2, 2019" (the post says the real story is "much more complex than a regular expression went bad"; visitors saw 502 pages for any Cloudflare domain) | opened |
| 1 | Perl over 60 s on a 29-character string vs about 20 µs for Thompson NFA | Russ Cox, swtch.com/~rsc/regexp/regexp1.html (2007); the pattern there is a?ⁿaⁿ, not the demo's | opened |
| 1 | Thompson, "Regular Expression Search Algorithm", CACM 11(6) 419–422 (June 1968): each character is examined against a list of all possible current characters while a list of next ones is built | the 4-page paper (oilshell.org archive copy), opened | opened |
| 1 | Demo: both matchers run the same 5 instructions of (a+)+b on n a's and count instructions executed; backtracker 5 × 2ⁿ − 4, state-set matcher 4n + 1 | own code; every slider length 1 to 22 checked in a browser against both formulas; the count for 40 characters comes from a memoised count of the same instructions | computed |
| 1 | Perl 5.34 rejects `^(a+)+b$` on 40 a's at once | run on this Mac on 23 Oct 2026 (V8 in node took 2.6 s at 24 a's on the same pattern) | computed |
| 2 | More than 10⁹ items, typical accuracy 2%, 1.5 kilobytes, 1.04/√m, m = 2048, 32-bit hash, registers of 5 bits | Flajolet, Fusy, Gandouet, Meunier 2007, algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf, abstract and introduction ("using m = 2048, hashing on 32 bits, and short bytes of 5 bit length each ... 1.5kB"); 2,048 × 5 bits is 1,280 bytes, so the paper rounds up | opened |
| 2 | Google implementation, 2013 | Heule, Nunkesser, Hall, "HyperLogLog in Practice", Google Research page, abstract ("implemented ... for a system at Google") | opened (abstract) |
| 2 | 2,048 registers × 6 bits = 1,536 bytes (the demo's packed array, byteLength shown on the page); 1.04/√2048 = 2.3%; a billion 4-byte IDs = 4 GB; a hash starting with ten zeros about once in 1,024 items; about three runs in ten fall outside 2.3% | own arithmetic and a 150-run browser test (29% outside 2.3% at 100,000 items) | computed |
| 3 | Gale–Shapley 1962, AMM 69(1) 9–15; Theorem 2: every proposer gets the best partner any stable assignment gives | the paper (JSTOR cover page reads pp. 9–15), opened by Codex and checked here | opened |
| 3 | Receivers get their worst stable partner; proposers cannot gain by lying, receivers sometimes can | Wikipedia "Gale–Shapley algorithm"; the 1962 paper does not state the receiver-worst part in so many words | opened (reference work) |
| 3 | Nobel 2012, Roth and Shapley, "the theory of stable allocations and the practice of market design" | nobelprize.org press release, 15 October 2012 | opened |
| 3 | Demo: all 6 pairings tried, 3 stable (proposer-optimal, receiver-optimal, one where everyone gets their second choice) | own code, run in node and in the browser | computed |
| 4 | Bloch, 2 June 2006; mid = (low + high) / 2 overflows past 2,147,483,647; JDK version Bloch wrote had it, "lying in wait for nine years or so", broke someone's program; Bentley's version proved correct and tested in "Chapter 5" of Programming Pearls, undetected "for two decades" | research.google blog post | opened |
| 4 | JDK-5045582 "binarySearch() fails for size larger than 1<<30", created 11 May 2004, fixed in 6 | Internet Archive copy of the bugs.openjdk.org record (the live site was down) | opened |
| 4 | Bentley's book and the chapter or column number | not opened; the page follows Bloch's wording | not opened |
| 4 | "A proof that treats whole numbers as unlimited cannot catch this" | general reasoning, not a claim about Bentley's proof | own reading |
| 5 | Ellis January 1970; Cocks 20 November 1973; Williamson 21 January 1974 | the three original notes, cryptocellar.org/cesg/ (possnse.pdf, notense.pdf, secenc.pdf) | opened |
| 5 | Cocks "what we now call RSA", Williamson "essentially Diffie–Hellman"; made public December 1997 | CESG, "The History of Non-Secret Encryption", mirrored on cryptome.org and dated 4 February 1998 (the page says Ellis's paper was released in December 1997; the cesg.gov.uk original no longer loads; found by Codex, checked here) | opened (mirror) |
| 5 | Diffie and Hellman, IEEE Trans. Inf. Theory 22(6) 644–654, November 1976; acknowledges Merkle's independent work (p. 648) | the paper (Stanford copy) | opened |
| 5 | Merkle, CACM 21(4), April 1978, received August 1975 | Merkle's paper, opened by Codex | opened |
| 5 | RSA devised 1977, published 1978 | Wikipedia "Public-key cryptography"; the CESG page gives 1978 for the academic RSA | opened (reference work) |
| 5 | 2,048-bit primes in use (617 decimal digits); Curve25519 over 2²⁵⁵ − 19 (77 digits) | RFC 7919 (ffdhe2048 and larger) and RFC 7748 §4.1; digit counts computed | opened; computed |
| 5 | 2⁶¹ − 1 is prime (19 digits) | Lucas–Lehmer test run in node, see below | computed |
| 6 | Rule 110 = 01101110; Wolfram's 1985 conjecture proved by Cook, Complex Systems 15(2004) 1–40 | Cook's paper, wpmedia.wolfram.com (the first page states the conjecture and the journal reference) | opened |
| 6 | Needs a particular repeating background | Wikipedia "Rule 110"; Cook's paper | opened (reference work) |
| 6 | "Rule 30 looks random, rule 90 draws a regular triangle" | visible in the demo | not individually sourced |
| 7 | BB(5) search completed 2 July 2024; champion 47,176,870 steps, 5-state 2-symbol, blank tape; Marxen and Buntrock 1990; 88,664,064 undecided machines | bbchallenge.org/story | opened |
| 7 | Found 1989 (Wikipedia) or 1990 (bbchallenge); proof formalised in Rocq; S(3) = 21, S(4) = 107; Σ(3) = 6, Σ(4) = 13, Σ(5) = 4,098; Σ(6) > 2↑↑↑5; 745-state machine for ZFC and later claims down to 230 states | Wikipedia "Busy beaver" (current text) | opened (reference work) |
| 7 | State counts of machines that halt iff ZF/ZFC is inconsistent: 7,910 (2016), 745 (July 2023), then smaller; 230 on 19 October 2026 | wiki.bbchallenge.org/wiki/Logical_independence (the page lists these as claims with proof-assistant files; the table is headed ZF, Wikipedia says ZFC) | opened |
| 7 | Demo machines reproduce 21, 107, 47,176,870 steps and 4, 13, 4,098 ones; the five-state table matches the one on bbchallenge | own simulation, node and browser | computed |
| 8 | Freivalds 1977; O(kn²); error at most 1/2 per round; direct product n³, best known about n^2.372 | Wikipedia "Freivalds' algorithm"; the 1977 paper's text could not be opened (DBLP record opened, no full text; Raghavan's survey blocked); the 1/2 bound is also shown by the demo (a single changed entry is missed when its random coordinate is 0) | opened (reference work) |
| 9 | Time t in O(√(t log t)) space for multitape Turing machines; "a little progress on the P versus PSPACE problem"; builds on Cook–Mertz, STOC 2024; to appear at STOC 2025 | arXiv:2502.17779, abstract and Theorem 1.1 in the paper | opened |
| 9 | Previous bound t/log t, Hopcroft–Paul–Valiant, JACM 24(2) 332–337 (1977), Theorem 1 | the paper, opened by Codex; Williams's abstract cites it | opened |
| 9 | Cook and Mertz, "Tree Evaluation is in Space O(log n · log log n)", ECCC TR23-174, 15 November 2023, STOC 2024 | ECCC report page; Williams cites STOC 2024 | opened |
| 9 | "The theorem does not say how long the memory-saving version takes" | Theorem 1.1 states a space bound only | opened |
| 10 | Theorem 1 (elastic hashing, non-greedy: O(1) amortised, O(log 1/δ) worst-case expected); Theorem 2 (funnel hashing, greedy: O(log² 1/δ) worst-case expected, plus log log n for the high-probability version); matching lower bounds Ω(log² 1/δ) for greedy schemes, Ω(log 1/δ) for all schemes without reordering; Yao's 1985 results and conjecture | arXiv:2501.02305v2 (HTML), introduction and Sections 2 to 5 | opened |
| 10 | Krapivin an undergraduate at Rutgers in fall 2021 and later; now a graduate student at Cambridge; Cambridge affiliation on the paper; about 100 probes at 99% full | Quanta Magazine, 10 February 2025; arXiv author line; Rutgers Honors College page (class of 2024, Churchill Scholar) | opened |
| 10 | Demo: random probing needs about 2, 10, 100 probes near 50%, 90%, 99% | own simulation (matches 1/(1 − load)): 2.0, 10.2, 98 in the last browser run | computed |

2⁶¹ − 1: Lucas–Lehmer test run in node on 23 October 2026: s₀ = 4, sᵢ₊₁ = sᵢ² − 2 mod M, 59 iterations (p − 2) for p = 61, final s = 0, so 2⁶¹ − 1 is prime.

Dropped: the PCP theorem (checking a proof by reading three bits) and Dijkstra's shortest-path sorting barrier (2025): both held for lack of time to open the papers.