Lamé’s theorem: Euclid’s worst case is Fibonacci
Theorem.Lamé’s theorem: Euclid’s worst case is Fibonacci — steps(F_{n+1},F_n) equals the exhaustive maximum over all pairs a ≤ F_{n+1}, b ≤ F_n for n = 3..12.
Proof.steps(F_{n+1},F_n) equals the exhaustive maximum over all pairs a ≤ F_{n+1}, b ≤ F_n for n = 3..12 — consecutive Fibonacci numbers are the slowest input, the 1844 result that founded computational complexity.
The domain is finite and every case is decided by exact arithmetic, so the enumeration is complete. ∎
src/4/6/index.ts#discoveredTheoremsWaveSixtyTwo
1 · Classification
finite-complete — self-contained computation, no external lean
2 · Provenance
Documented theorem re-derived by exhaustive computation (humanityNovel=false); first-in-this-registry is the only sense of discovered.
Acknowledgment
"Lamé’s theorem: Euclid’s worst case is Fibonacci" is a re-derivation, acknowledged to documented mathematics — the original proof is the prior art this re-derivation acknowledges; not new to humanity — the contribution is the reproducible computation discoveredTheoremsWaveSixtyTwo.
- Prior art
- documented mathematics — the original proof is the prior art this re-derivation acknowledges
- Novelty
- not new to humanity — a re-derivation (humanityNovel = false)
- Contribution
- a reproducible computation (discoveredTheoremsWaveSixtyTwo @ src/4/6) that re-derives the result at zero tokens — the contribution is the verifiable recomputation, NOT the theorem
3 · Reproducibility
Recompute from source: npm run theorems:verify recomputes discoveredTheoremsWaveSixtyTwo (src/4/6/index.ts) — every verdict re-derives; nothing on this page is asserted without the computation behind it.