How many numbers are left in the set 1 2 1000 after all mul

How many numbers are left in the set {1, 2, ..., 1000} after all multiples of 2, 3, 5, and 7 are crossed out?

Solution

Let Ai be the number of numbers in {1,..., 1000} that are multiples of i.

We have |A2| = 500, |A3| = 333, |A5| = 200, |A7| = 142, |A2\\A3| = 166, |A2\\A5| = 100, |A2\\A7| = 71, |A3\\A5| = 66, |A3\\A7| = 47, |A5\\A7| = 28, |A2 \\ A3 \\ A5| = 33, |A2 \\ A3 \\ A7| = 23, |A2 \\ A5 \\ A7| = 14, |A3 \\ A5 \\ A7| = 9 and |A2 \\ A3 \\ A5 \\ A7| = 4. (To calculate |A2 \\ A3 \\ A5| note that being in A2 \\ A3 \\ A5 is equivalent to being divisible by all of 2, 3 and 5, which is equivalent to being divisible by 2.3.5 = 30, so A2 \\ A3 \\ A5 is the set of multiples of 30 at or below 1000; since 1000/30 = 33.33 ..., there are 33 such multiples; the rest of the sets are calculated in the same way). By inclusion-exclusion, |A2 [ A3 [ A5 [ A7| is (500 + 333 + 200 + 142) (166 + 100 + 71 + 66 + 47 + 28) + (33 + 23 + 14 + 9) 4 = 772. So there are 772 multiples of 2, 3, 5 and 7 that get crossed out, leaving 228 numbers.