cycle_greedy_moments_all_fuel
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
iof a gap listgrepresenting distances between free facilities on a cycle, combining gaps…
- cycle_gap_mergeMerges the adjacent gaps at cyclic index
- 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