AFTD Auto-Formalizing Theoretical Domains

mixed_radix_offset

def

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)
See it in the graphDiscuss this resultChallenge it