mixed_radix_offset
Given a table size n, an ordered list of factors P, and an index j in Fin n, mixed_radix_offset n P j is the element of ZMod n given by the sum over i : Fin P.length of ((j.val / (P.take i.val).prod) % P[i.val] : ZMod n) * ((n / (P.take (i.val + 1)).prod : ℕ) : ZMod n).
Statement
def mixed_radix_offset (n : ℕ) (P : List ℕ) (j : Fin n) : ZMod n- Defined in
- arXiv:2610.31363
- Verified
- 01 Nov 2026
- Axioms
- none listed
- Used by 4
- mixed_radix_offset_mean_probe_zeroFor every table size n ≥ 2, every probe sequence r : Fin n → ZMod n, and every factor list P, the expected probe cost into an empty table…
- fixed_offset_hash_worst_mean_mixed_radix_primeFor any prime p, any bijective offset sequence r : Fin p → ZMod p, and any load t < p, if linear probing achieves expected probe cost at…
- mixed_radix_offset_bijectiveFor any table size n ≥ 2 and any permutation P of the prime factors of n, the mixed-radix reversed offset sequence mixed_radix_offset n P…
- mixed_radix_offset_primeFor any positive integer p and any index j in Fin p, the mixed-radix reversed offset with singleton factor list [p] equals the linear…
Read back from the Lean
Given a natural number n, a list of natural numbers P, and an index j : Fin n, mixed_radix_offset n P j defines an element of ZMod n as the sum over all i : Fin P.length of the product of:
1. (j.val / (P.take i.val).prod) % P[i.val], computed in ℕ and cast to ZMod n, and
2. n / (P.take (i.val + 1)).prod, computed in ℕ (using truncated division) and cast to ZMod n.
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 mixed-radix reversed offset sequence for table size n and ordered factors P. -/ def mixed_radix_offset (n : ℕ) (P : List ℕ) (j : Fin n) : ZMod n := ∑ i : Fin P.length, (((j.val / (P.take i.val).prod) % P[i.val] : ℕ) : ZMod n) * ((n / (P.take (i.val + 1)).prod : ℕ) : ZMod n)