cycle_greedy_moments_fuel
A function with signature (fuel : ℕ) → (n : ℕ) → (g : List ℕ) → ℚ × ℚ. If fuel = 0, it returns (0, 0). If fuel = 1 or g.length ≤ 1, letting m : ℚ := g.head?.getD 0, it returns terminal cost (m / 4, m ^ 2 / 12). For fuel + 1 with fuel ≥ 1 and g.length > 1, it computes the fold over i ∈ [0, g.length) starting from (0, 0) with accumulator update (acc.1 + c + p * sub1, acc.2 + d + 2 * c * sub1 + p * sub2), where l := g[(i + k - 1) % k]?.getD 0, r := g[i]?.getD 0, p := (l + r) / (2 * n), c := (l^2 + r^2) / (8 * n), d := (l^3 + r^3) / (24 * n), and (sub1, sub2) evaluates cycle_greedy_moments_fuel fuel n (cycle_gap_merge g i).
Statement
def cycle_greedy_moments_fuel : ℕ → ℕ → List ℕ → ℚ × ℚ- Defined in
- arXiv:2610.15776, Corollary 18 and Appendix A.2
- Verified
- 02 Nov 2026
- Axioms
- none listed
- Built on 1
- cycle_gap_mergeMerges the adjacent gaps at cyclic index
iof a gap listgrepresenting distances between free facilities on a cycle, combining gaps…
- cycle_gap_mergeMerges the adjacent gaps at cyclic index
- Used by 3
- cycle_greedy_second_moment_twoFor n = 2, the exact rational second moment equals the conjectured formula value:…
- cycle_greedy_momentsThe function
cycle_greedy_moments (n : ℕ) (g : List ℕ) : ℚ × ℚdefined ascycle_greedy_moments_fuel g.length n g. - cycle_greedy_second_moment_threeFor n = 3, the exact rational second moment equals the conjectured formula value:…
Read back from the Lean
cycle_greedy_moments_fuel is a function taking three arguments: a fuel parameter fuel : ℕ, a normalizer n : ℕ, and a list of natural numbers g : List ℕ, and returning a pair of rational numbers (ℚ × ℚ). It is defined by recursion on fuel:
1. **fuel = 0**: Returns (0, 0).
2. **fuel = 1**: Let m : ℚ be the head of g (or 0 if g is empty). Returns (m / 4, m^2 / 12).
3. **fuel + 1** (where fuel ≥ 1):
Let k = g.length.
- If k ≤ 1: Let m : ℚ be the head of g (or 0 if g is empty). Returns (m / 4, m^2 / 12).
- If k > 1: Folds over the indices i in [0, k - 1] (List.range k) with initial accumulator acc = (0, 0):
For each index i:
- Let l : ℚ be g[(i + k - 1) % k] (the element cyclically preceding index i, or 0 if out of bounds).
- Let r : ℚ be g[i] (the element at index i, or 0 if out of bounds).
- Let next_g := cycle_gap_merge g i.
- Recursively compute (sub1, sub2) := cycle_greedy_moments_fuel fuel n next_g.
- Let p : ℚ := (l + r) / (2 * n).
- Let c : ℚ := (l^2 + r^2) / (8 * n).
- Let d : ℚ := (l^3 + r^3) / (24 * n).
- Update the accumulator to:
(acc.1 + c + p * sub1, acc.2 + d + 2 * c * sub1 + p * sub2).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Exact dynamic programming recursion with fuel computing first and second moments of remaining greedy assignment cost from gap state g. -/ def cycle_greedy_moments_fuel : ℕ → ℕ → List ℕ → ℚ × ℚ | 0, _, _ => (0, 0) | 1, _, g => let m : ℚ := g.head?.getD 0 (m / 4, m ^ 2 / 12) | fuel + 1, n, g => let k := g.length if k ≤ 1 then let m : ℚ := g.head?.getD 0 (m / 4, m ^ 2 / 12) else (List.range k).foldl (fun (acc : ℚ × ℚ) (i : ℕ) => let l : ℚ := g[(i + k - 1) % k]?.getD 0 let r : ℚ := g[i]?.getD 0 let next_g := cycle_gap_merge g i let (sub1, sub2) := cycle_greedy_moments_fuel fuel n next_g let p : ℚ := (l + r) / (2 * n) let c : ℚ := (l ^ 2 + r ^ 2) / (8 * n) let d : ℚ := (l ^ 3 + r ^ 3) / (24 * n) (acc.1 + c + p * sub1, acc.2 + d + 2 * c * sub1 + p * sub2) ) (0, 0)