skip to content

Using inclusion-exclusion, how do you count the IDs from 1 to 1000 divisible by none of 2, 3 and 5?

level: middleimportance: must knowfreq 50%

answer

  1. count multiples with floor division
  2. pairwise overlap means the least common multiple
  3. add pairs back, subtract the triple
  4. 1033 - 332 + 33 = 734 caught
  5. survivors are 1000 minus the union

basics

~10 s

Subtract from 1000 the multiples of 2, 3 and 5, add back the multiples of 6, 10 and 15, then subtract the multiples of 30. That is 1000 - 734 = 266 surviving IDs.

solid answer

~40 s

Count the multiples of each divisor with floor division: 500, 333 and 200. Those tallies double count anything divisible by two of the divisors, so add back the multiples of their pairwise least common multiples - `floor(1000/6) = 166`, `floor(1000/10) = 100`, `floor(1000/15) = 66` - and then subtract the multiples of `lcm(2,3,5) = 30`, which is 33. The union is `500 + 333 + 200 - 166 - 100 - 66 + 33 = 734`, so `1000 - 734 = 266` IDs survive. The key step is that the intersection of two divisibility conditions is divisibility by their **least common multiple**, not by their product - that shortcut only coincides for coprime divisors.

code

pseudocode · 10 lines
pseudocode
N = 1000

singles = floor(N/2) + floor(N/3) + floor(N/5)        // 500 + 333 + 200 = 1033
pairs   = floor(N/6) + floor(N/10) + floor(N/15)      // 166 + 100 +  66 =  332
triple  = floor(N/30)                                 //                    33

union     = singles - pairs + triple                  // 734
survivors = N - union                                 // 266

return survivors

go deeper

for a junior

Recall that the multiples of d up to N number floor(N/d), and that adding the counts for several divisors double counts anything divisible by two of them.

for a middle

Explain the full signed sum, and show you compute pairwise overlaps through least common multiples rather than products - the coprime case hides that distinction.

for a senior

Show you sanity-check the result against the density 4/15 before trusting it, and that you state the range convention rather than assume one.

for a principal

Judge whether divisibility-based reservation is the right partitioning scheme at all, given that overlapping rules make the reserved share hard to reason about as rules are added.

## Why this shape of problem keeps coming up A sharding or sampling scheme frequently reserves identifiers by divisibility: every second ID goes to a mirror, every third is sampled for audit, every fifth is held back for canary traffic. The question that follows is how many IDs are left untouched by **any** of those rules - the ones that flow through the ordinary path. It is the same clean-count shape as a set of taint filters, except that here the intersection sizes are free: you never have to scan the IDs, because divisibility has closed-form counts. ## The two facts the count rests on 1. **Counting multiples.** The number of integers in `1..N` divisible by `d` is exactly `floor(N/d)`. There is no rounding error to correct; the multiples are `d, 2d, ... , floor(N/d) x d`. 2. **Intersecting two divisibility conditions.** An integer divisible by both `a` and `b` is exactly an integer divisible by `lcm(a,b)`. For coprime divisors that is the product, which is why `2` and `3` intersect at `6`; for `2` and `4` it is `4`, not `8`. Getting this wrong is the single most common error in this family, and it is invisible until a non-coprime pair appears. ## Working it through With `N = 1000` and divisors `2, 3, 5`: | term group | values | signed subtotal | |---|---|---| | singles | 500, 333, 200 | +1033 | | pairs (lcm 6, 10, 15) | 166, 100, 66 | -332 | | triple (lcm 30) | 33 | +33 | | union | | 734 | | survivors | 1000 - 734 | **266** | A sanity check comes free from densities. The three divisors are pairwise coprime, so the fraction of integers surviving all three conditions tends to `(1/2) x (2/3) x (4/5) = 4/15`, and `4/15 x 1000 = 266.67`. The exact count, 266, sits where it should - just under the density estimate because 1000 is not a multiple of 30. Any answer far from that density is arithmetic to redo. ## Why the survivors are not simply a product The density shortcut works here only because the divisors are pairwise coprime; multiplying `1 - 1/d` over the divisors silently assumes the conditions behave independently. Over an initial segment `1..N` that is an approximation, exact only when `N` is a multiple of the overall least common multiple - here, of 30. Inclusion-exclusion is the exact statement, and the product is the asymptotic shadow of it. When the divisors share factors, the product form is not even asymptotically right, while the signed sum with correct least common multiples still is. ## Term count and the practical ceiling With three divisors the sum has `2^3 = 8` terms: one empty term supplying `N`, three singles, three pairs, one triple. With `k` divisors it is `2^k`. For the handful of small primes a sharding scheme uses, that is trivial. For twenty conditions it is over a million terms, and the method stops being the sensible route - but note that each term is a division here, not a database scan, so this variant scales further than the general case does. ## Related traps - **Off-by-one on the range.** `floor(N/d)` counts `1..N`. If the range is `0..N`, zero is divisible by everything and the counts shift by one - state the range before you start. - **Inclusive upper bounds.** For `a..b` the count of multiples of `d` is `floor(b/d) - floor((a-1)/d)`; substituting `a = 1` recovers the simple form. - **Composite divisors.** With divisors `4` and `6`, the pairwise term is `lcm(4,6) = 12`, not `24`. Half the classic mistakes in this family are exactly this. - **Reporting the wrong side.** 734 is the count caught by at least one rule; 266 is the count caught by none. They are trivially related and constantly confused in a hurry. ## What an interviewer is checking Not the long division. They want to see that you reach for the signed sum rather than adding tallies, that you compute the intersections through least common multiples rather than products, that you keep the complement straight, and that you can sanity-check the result against a density in one line. Doing the arithmetic out loud and then failing the density check is a worse outcome than stating the structure and checking it.

  • The divisors become 4 and 6 instead of 2 and 3 - what changes in the sum?
    Only the pairwise term, and it is the step most people get wrong. The intersection is divisibility by `lcm(4,6) = 12`, not by the product 24, so the term is `floor(N/12)`. The singles are unchanged. Using the product would subtract too little and inflate the survivor count.
  • Why does multiplying the surviving fractions not give the exact answer?
    Multiplying `(1 - 1/d)` over the divisors treats the conditions as independent, which is exactly true only when `N` is a multiple of the overall least common multiple. Here `4/15 x 1000 = 266.67` against an exact 266. The product is the density limit; the signed sum is the count.
  • Does the range start at 0 or 1, and does it matter?
    It matters. `floor(N/d)` counts the multiples in `1..N`. Zero is divisible by every divisor, so including it adds one to every single, pair and triple term and removes one survivor. For a general range `a..b` use `floor(b/d) - floor((a-1)/d)` per term.

saying these in an interview costs you the question

  • Intersecting two divisibility rules by multiplying the divisors
  • Adding the three multiple counts and subtracting once from 1000
  • Forgetting the three-way term for multiples of 30
  • Reporting 734 when the question asked for the survivors
  • Assuming the product of surviving fractions is exact for any N