AFTD Auto-Formalizing Theoretical Domains

range_card_filter_dvd

theoremverified

For m > 0, the numbers 0, ..., k-1 include exactly ceil(k/m) = (k + m - 1)/m multiples of m.

Statement

theorem range_card_filter_dvd (m k : ℕ) (hm : 0 < m) :
    ((Finset.range k).filter (fun j => m ∣ j)).card = (k + m - 1) / m
Source
step towards weakly_consecutive_one_at_end_of_isPrimePow (Weakly Consecutive Sequences (2024), arXiv:2401.09497, Conjecture 5.2, prime-power case)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • fin_card_filter_dvdFor m > 0, exactly (k + m - 1)/m of the positions 0, ..., k-1 are multiples of m.

Lean source view module on GitHub

theorem range_card_filter_dvd (m k : ℕ) (hm : 0 < m) :    ((Finset.range k).filter (fun j => m ∣ j)).card = (k + m - 1) / m := by  induction k with  | zero => simp; exact (Nat.div_eq_of_lt (by omega)).symm  | succ k ih =>    rw [Finset.range_add_one, Finset.filter_insert]    have e : k + 1 + m - 1 = (k + m - 1) + 1 := by omega    rw [e, Nat.succ_div, ← ih]    have e2 : k + m - 1 + 1 = k + m := by omega    rw [e2]    by_cases h : m ∣ k    · have h' : m ∣ k + m := (Nat.dvd_add_self_right).2 h      rw [if_pos h, if_pos h', Finset.card_insert_of_notMem (by simp)]    · have h' : ¬ m ∣ k + m := fun h' => h ((Nat.dvd_add_self_right).1 h')      rw [if_neg h, if_neg h']      simp
See it in the graphDiscuss this resultChallenge it