cycle_gap_merge
Merges the adjacent gaps at cyclic index i of a gap list g representing distances between free facilities on a cycle, combining gaps (i - 1) % g.length and i when g.length > 1.
Statement
def cycle_gap_merge (g : List ℕ) (i : ℕ) : List ℕ- Defined in
- arXiv:2610.15776, Section 4 and Corollary 18
- Verified
- 02 Nov 2026
- Axioms
- none listed
- Used by 6
- cycle_gap_merge_pairMerging two unit gaps at index 0 on a cycle yields a single gap of length 2.
- cycle_greedy_moments_all_fuelA recursive function with signature
(fuel : ℕ) → (k_max : ℕ) → (n : ℕ) → (g : List ℕ) → List ℚ. Iffuel = 0, it returns the empty… - 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_second_moment_twoFor n = 2, the exact rational second moment equals the conjectured formula value:…
- cycle_greedy_second_moment_threeFor n = 3, the exact rational second moment equals the conjectured formula value:…
- cycle_greedy_moments_fuelA function with signature
(fuel : ℕ) → (n : ℕ) → (g : List ℕ) → ℚ × ℚ. Iffuel = 0, it returns(0, 0). Iffuel = 1or…
Read back from the Lean
cycle_gap_merge is a function that takes a list of natural numbers g and a natural number i, and returns a List ℕ defined as follows:
Let k = g.length.
- If k ≤ 1, it returns g.
- Otherwise (if k > 1):
Let idx = i % k.
- If idx = 0, it returns g.tail.dropLast ++ [(g.getLast?.getD 0) + (g.head?.getD 0)], which removes the first and last elements of g and appends their sum to the end (yielding a list of length k - 1).
- If idx ≠ 0, it returns g.take (idx - 1) ++ ((g[idx - 1]?.getD 0) + (g[idx]?.getD 0)) :: g.drop (idx + 1), which replaces the two adjacent elements at indices idx - 1 and idx with their sum (also yielding a list of length k - 1).
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
/-- Merges adjacent gaps at cyclic index i upon consuming the intervening facility. -/ def cycle_gap_merge (g : List ℕ) (i : ℕ) : List ℕ := let k := g.length if k ≤ 1 then g else let idx := i % k if idx = 0 then (g.tail.dropLast) ++ [(g.getLast?.getD 0) + (g.head?.getD 0)] else g.take (idx - 1) ++ ((g[idx - 1]?.getD 0) + (g[idx]?.getD 0)) :: g.drop (idx + 1)