How many integers from 1 through 1000 are divisible by 3 and by at least one of 2,5,7, and 11?

Question

So I got 294 for this question, though I'm not a hundred percent sure but let me explain my process:

I did

to find all the multiples: (floor of each)

1000/6 = 166 1000/15 = 66 1000/21 = 47 1000/33 = 30 166+66+47+30 = 309

to eliminate the repeats: (floor of each)

66/6 = 11 47/6 = 7 30/6 = 5 47/15 = 3 30/15 = 2 30/21 = 1

11+7+5+3+2+1 = 29

to add in the repeats that were eliminated twice over: (floor of each)

5/2 = 2 7/2 = 3 11/2 = 5 7/5 = 1 11/5 = 2 11/7 = 1

2+3+5+1+2+1 = 14

309 - 29 + 14 = 294

Answer 1

If you consider the range $3$ to $999$, divide by $3$, then we find that your question is equivalent to the following simpler question:

how many integers between $1$ and $333$ are divisible by at least one of $2$, $5$, $7$, or $11$?

For this question we may use inclusion-exclusion.

---

Multiples of $2,5,7,11$ with much overcounting:

$$\left\lfloor \frac{333}{2} \right\rfloor + \left\lfloor \frac{333}{5} \right\rfloor + \left\lfloor \frac{333}{7} \right\rfloor + \left\lfloor \frac{333}{11} \right\rfloor $$

Subtract these terms:

$$ \left\lfloor \frac{333}{10} \right\rfloor + \left\lfloor \frac{333}{14} \right\rfloor + \left\lfloor \frac{333}{22} \right\rfloor + \left\lfloor \frac{333}{35} \right\rfloor + \left\lfloor \frac{333}{55} \right\rfloor + \left\lfloor \frac{333}{77} \right\rfloor $$

Add back these terms:

$$ \left\lfloor \frac{333}{70} \right\rfloor + \left\lfloor \frac{333}{110} \right\rfloor + \left\lfloor \frac{333}{154} \right\rfloor + \left\lfloor \frac{333}{385} \right\rfloor $$

Since $770>333$, there are no multiples of $770$ that we have to worry about having overcounted.