How many numbers between 1 and 1000 are divisible by 2, 3, 5 or 7?
My try:
Let $A_2, A_3, A_5, A_7$ be the set of numbers between 1 and 1,000 that are divisible by 2, 3, 5, and 7 respectively. I used the inclusion-exclusion formula for $|A_2\cup A_3\cup A_5\cup A_7|= |A_2|+|A_3|+|A_5|+|A_7|-|A_2\cap A_3|-|A_2\cap A_5|-|A_2\cap A_7|-|A_3\cap A_5|-|A_3\cap A_7|-|A_5\cap A_7|+|A_2\cap A_3\cap A_5|+|A_2\cap A_3\cap A_7|+|A_2\cap A_5\cap A_7|+|A_3\cap A_5\cap A_7|-|A_2\cap A_3\cap A_5\cap A_7| = 500+333+200+142-166-100-71-66-47-28+33+23+14+9-4 = 772 $
And the result I received was – 772.
I would appreciate if you could confirm my method and result, and I'd be happy to see a different, more elegant approach.
Best Answer
The totient of $210$ - the number of values between $1$ and $210$ that are relatively prime to $210$ - is $(2-1)(3-1)(5-1)(7-1)=48$. Using this, we can say that there are $48\cdot5=240$ numbers not divisible by these four numbers up to $1050$. Some of these of course are out of range of the original question; we'll have to figure out what those are.
The totient of $30$ is $8$; from $991$ to $1050$ there are $16$ numbers relatively prime to $30$. We'll take these out for now, leaving $224$. But two numbers we removed - $1001$ and $1043$ - are divisible by $7$ and so weren't part of the original $240$ so we have to un-remove them, adding them back to the total. Further, $991$ and $997$ are below $1000$ so shouldn't have been removed either. This gives $224+2+2=228$ numbers relatively prime to $210$, so $1000-228=772$ numbers are divisible by $2$, $3$, $5$, or $7$.