AFTD Auto-Formalizing Theoretical Domains

cycle_greedy_moments_fuel

def

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 i of a gap list g representing distances between free facilities on a cycle, combining gaps…
Used by 3

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)
See it in the graphDiscuss this resultChallenge it