Not divisible by $2,3$ or $5$ but divisible by $7$

Question

The question is to determine the number of positive integers up to $2000$ that are not divisible by $2,3$ or $5$ but are divisible by $7$. The answer is supposed to be $76$ but not sure how it was derived

I know that if the question was how many integers are not divisible by $2,3,5$ or $7$ then the answer would be $458$ and I know how to derive this.

Answer 1

You can solve this with inclusion-exclusion. First look for how many numbers are divisible by $7$: that's $\lfloor 2000/7 \rfloor = 285$, the integer part of $2000/7$.

Now exclude those that are divisible by $2$ (multiples of $14$; there are $\lfloor 2000/14 \rfloor$), divisible by $3$ ($\lfloor 2000/21 \rfloor$) and divisible by $5$ ($\lfloor 2000/35 \rfloor$).

This is excluding too many. Add back those that you removed twice or more: $\lfloor 2000/42 \rfloor + \lfloor 2000/70 \rfloor + \lfloor 2000/105 \rfloor$.

Finally, exclude again those that are divisible by all of $2,3,$ and $5$: these are multiples of $2\cdot 3 \cdot 5 \cdot 7 = 210$ and there are $\lfloor 2000/210 \rfloor$ such.

Answer 2

Hint: Given any number $n$ not divisible by $2,3,5$, we get that $7n$ is divisible by $7$ and not divisible by $2,3,5.$ And visa versa.

Answer 3

\begin{align}\# \text{ of numbers divisible by }7\text{ but not by }2,3 \text{ or }5 & = \#\text{ of numbers divisible by }7\\ & - \#\text{ of numbers divisible by 7 and 2, i.e., by 14}\\ & - \#\text{ of numbers divisible by 7 and 3, i.e., by 21}\\ & - \#\text{ of numbers divisible by 7 and 5, i.e., by 35}\\ & + \#\text{ of numbers divisible by 7 and 2 and 3, i.e., by 42}\\ & + \#\text{ of numbers divisible by 7 and 2 and 5, i.e., by 70}\\ & + \#\text{ of numbers divisible by 7 and 3 and 5, i.e., by 105}\\ & - \#\text{ of numbers divisible by 7 and 2 and 3 and 5, i.e., by 210} \end{align}

Answer 4

$2000/7= 285+5/7$ so there are $285$ positive multiples of $7$ less than $2000$

Out of every $30$ such multiples $15$ are divisible by $2$, of the remaining $15$, $5$ are divisible by $3$, and of the remaining $10$, $2$ are divisible by $5$ (note the pattern). So this leaves $8$ in every $30$ divisible by $7$ alone.

$285 = 9\cdot 30 +15$. So we have $8\cdot 9=72$ such multiples up to $270$, and it is easy to check $4$ more in the final $15$.

You will spot some patterns here which might lead you to a more efficient general approach. I've suggested "by hand" because it might help you to see why the patterns work - it did the trick for me, many years ago!