AFTD Auto-Formalizing Theoretical Domains

hash_total_probe_cost

def

For a table of size n, an offset sequence r : Fin n → ZMod n, and a list of inserted key home slots A : List (ZMod n), hash_total_probe_cost n r A is the sum of the numbers of probes used by all insertions when the keys in A are inserted sequentially into an initially empty table.

Statement

def hash_total_probe_cost (n : ℕ) (r : Fin n → ZMod n) (A : List (ZMod n)) : ℕ
Defined in
arXiv:2610.31363, Section 2
Verified
03 Nov 2026
Axioms
none listed

Read back from the Lean

hash_total_probe_cost n r A defines the total probe cost (as a natural number ℕ) of sequentially inserting elements of a list A : List (ZMod n) into a hash table with n : ℕ slots using the probe offset function r : Fin n → ZMod n. The calculation proceeds by folding over A starting with the initial state (∅, 0) consisting of an empty set of occupied slots Finset (ZMod n) and an initial cost of 0: For each element a in A: 1. It considers the set candidates of probe indices j : Fin n such that a + r j is not in the currently occupied set. 2. If candidates is nonempty, it takes the minimal index j_min = candidates.min', adds the slot a + r j_min to the set of occupied slots, and adds j_min.val + 1 (the 1-based probe count) to the accumulated cost. 3. If candidates is empty (all probed locations are already occupied), the state remains unchanged. The function returns the second component of the final state, which is the total accumulated probe cost.

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

/-- The total number of probes accumulated across sequential insertions of keys into an initially empty hash table under offset sequence r. -/
def hash_total_probe_cost (n : ℕ) (r : Fin n → ZMod n) (A : List (ZMod n)) : ℕ :=
  let step : Finset (ZMod n) × ℕ → ZMod n → Finset (ZMod n) × ℕ := fun state a =>
    have candidates : Finset (Fin n) := {j | a + r j ∉ state.1}
    if h : candidates.Nonempty then
      (state.1 ∪ {a + r (candidates.min' h)}, state.2 + (candidates.min' h).val + 1)
    else
      state
  (List.foldl step (∅, 0) A).2
See it in the graphDiscuss this resultChallenge it