AFTD Auto-Formalizing Theoretical Domains

cycle_greedy_moments_all_fuel

deforiginal

A recursive function with signature (fuel : ℕ) → (k_max : ℕ) → (n : ℕ) → (g : List ℕ) → List ℚ. If fuel = 0, it returns the empty list. If fuel = 1 or g.length ≤ 1, letting m : ℚ := g.head?.getD 0, it returns the list mapping each j ∈ [0, k_max] to (m / 2)^j / (j + 1). For fuel + 1 with g.length > 1, it initializes the accumulator to 1 :: List.replicate k_max 0 and folds over i ∈ [0, g.length), merging gaps at i and updating each moment m ∈ [1, k_max] by the binomial sum of the immediate cost moments (l^(j+1) + r^(j+1)) / (2^(j+1) * (j+1) * n) and subproblem moments sub.getD (m - j) 0.

Statement

def cycle_greedy_moments_all_fuel : ℕ → ℕ → ℕ → List ℕ → List ℚ
Related work
arXiv:2610.15776; OP-891
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 2
  • cycle_greedy_raw_moment_zeroThe zeroth raw moment of the greedy online assignment cost on an n-cycle is identically 1 for all n ≥ 2.
  • cycle_greedy_raw_momentThe exact rational k-th raw moment of total greedy facility assignment cost on a cycle of circumference n, computed via the fuel-bounded…

Read back from the Lean

cycle_greedy_moments_all_fuel is a function taking four arguments: 1. a fuel counter fuel : ℕ, 2. a maximum moment index k_max : ℕ, 3. a normalization parameter n : ℕ, 4. a list of natural numbers g : List ℕ, and returning a list of rationals List ℚ. It is defined by recursion on fuel: - If fuel = 0: returns the empty list []. - If fuel = 1: let m : ℚ be the first element of g (or 0 if g is empty); returns the list of length k_max + 1 whose j-th element (for j ∈ {0, ..., k_max}) is (m / 2)^j / (j + 1). - If fuel = fuel' + 1 (i.e., fuel ≥ 2 with predecessor fuel'): let k be the length of g. - If k ≤ 1: let m : ℚ be the first element of g (or 0 if g is empty); returns the list of length k_max + 1 with j-th element (m / 2)^j / (j + 1). - If k > 1: starting from an initial accumulator init = 1 :: List.replicate k_max 0, it iterates i through 0, ..., k - 1, at each step: - letting l : ℚ be g[(i + k - 1) % k] (defaulting to 0), - letting r : ℚ be g[i] (defaulting to 0), - letting next_g = cycle_gap_merge g i, - recursively computing sub = cycle_greedy_moments_all_fuel fuel' k_max n next_g, - and updating the accumulator to a list of length k_max + 1 whose m-th entry (for m ∈ {0, ..., k_max}) is: - 1 if m = 0; - acc[m] + term if m > 0, where term = ∑_{j=0}^m Nat.choose m j * ((l^(j+1) + r^(j+1)) / (2^(j+1) * (j + 1) * n)) * sub[m - j] (with sub[m - j] defaulting to 0 if out of bounds).

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

/-- Dynamic programming recurrence computing moments 0 through k_max of greedy cost on cycle gap configuration g with fuel. -/
def cycle_greedy_moments_all_fuel : ℕ → ℕ → ℕ → List ℕ → List ℚ
  | 0, _, _, _ => []
  | 1, k_max, _, g =>
    let m : ℚ := g.head?.getD 0
    (List.range (k_max + 1)).map (fun (j : ℕ) => (m / 2) ^ j / ((j : ℚ) + 1))
  | fuel + 1, k_max, n, g =>
    let k := g.length
    if k ≤ 1 then
      let m : ℚ := g.head?.getD 0
      (List.range (k_max + 1)).map (fun (j : ℕ) => (m / 2) ^ j / ((j : ℚ) + 1))
    else
      let init : List ℚ := 1 :: List.replicate k_max 0
      (List.range k).foldl (fun (acc : List ℚ) (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 sub := cycle_greedy_moments_all_fuel fuel k_max n next_g
        (List.range (k_max + 1)).map (fun (m : ℕ) =>
          if m = 0 then 1
          else
            let term : ℚ := (List.range (m + 1)).foldl (fun (t : ℚ) (j : ℕ) =>
              let ex_j : ℚ := (l ^ (j + 1) + r ^ (j + 1)) / (2 ^ (j + 1) * ((j : ℚ) + 1) * (n : ℚ))
              let ey : ℚ := sub.getD (m - j) 0
              t + (Nat.choose m j : ℚ) * ex_j * ey
            ) 0
            acc.getD m 0 + term
        )
      ) init
See it in the graphDiscuss this resultChallenge it