How many integers from 1 to 1000 inclusive are divisible by none of 2, 3, 5 and 7?

How many integers from 1 to 1000 inclusive are divisible by none of 2, 3, 5 and 7?

Approach: Count the multiples of each prime, subtract the overcount from pairs, add back the triples and remove the quadruple, taking floors at every stage since 1000 is not divisible by all the products.

228. Inclusion-exclusion counts the integers divisible by at least one of the four primes. Single counts are floor(1000/2) = 500, floor(1000/3) = 333, floor(1000/5) = 200 and floor(1000/7) = 142, summing to 1175. Pairs give floor(1000/6) = 166, floor(1000/10) = 100, floor(1000/14) = 71, floor(1000/15) = 66, floor(1000/21) = 47 and floor(1000/35) = 28, summing to 478. Triples give 33, 23, 14 and 9 for the products 30, 42, 70 and 105, summing to 79, and the quadruple 210 gives 4. So the divisible count is 1175 - 478 + 79 - 4 = 772, leaving 1000 - 772 = 228. The floor function matters because the exact fraction 1000 * (1/2)(2/3)(4/5)(6/7) = 228.57 differs from the true count. Those 228 are 1, the 164 primes above 7 below 1000, and the composites whose smallest prime factor is at least 11.

Follow-up: What does the same computation give as a density for the first N integers as N grows, and how does that relate to the prime counting function?

Key concepts: inclusion-exclusion principle, divisibility, floor function, counting.