Theorems · Theorem · number theory
Nat.roughNumbersUpTo_card_le
∀ (N k : ℕ), (N.roughNumbersUpTo k).card ≤ ∑ p ∈ (N + 1).primesBelow \ k.primesBelow, N / p
The cardinality of the set of k-rough numbers ≤ N is bounded by the sum of ⌊N/p⌋
over the primes k ≤ p ≤ N.
- Defined in
- Mathlib.NumberTheory.SmoothNumbers
- Cited by
- 1 results in Mathlib
- Foundations
- Depth 88 from the axioms · uses propext, Classical.choice, Quot.sound
Around this declaration
Dashed lines are statement dependencies; solid lines are citations in proofs.
Cites11
Mathlib declarations this one mentions in its statement or cites explicitly in its proof. Plumbing is filtered out.
- Finsetstatement and proof · cited by 13,712
- Finset.sumstatement and proof · cited by 5,195
- LE.le.transproof · cited by 3,151
- Finset.cardstatement and proof · cited by 2,327
- Eq.leproof · cited by 605
- Finset.sum_le_sumproof · cited by 182
- Nat.primesBelowstatement and proof · cited by 43
- Finset.card_biUnion_leproof · cited by 8
- Nat.roughNumbersUpTostatement · cited by 5
- Nat.card_multiples'proof · cited by 1
- Nat.roughNumbersUpTo_eq_biUnionproof · cited by 1
Cited by1
Results whose statement or proof uses this declaration.
- Nat.roughNumbersUpTo_card_le'proof · cited by 1