How many numbers between 1-10000 cannot be divided by 2 or 3?

Question

• I know that $5000$ are divisible by $2$ and $3333$ are divisible by $3$, but this will include repeats.
• I figured out that for numbers divisible by $3$, $1/3$ of them are divisible by $2$, so for the numbers divisible by $3$ that aren't divisible by $2$ will be $2222$.

$5000$ + $2222$ = $7222$ are divisible by $2$ or $3$, giving a final answer of $2778$.

What do you guys think $?$.

Answer 1

Let $M_d = \{\text{integers } n \text{ divisible by } d \text{ such that } 0 < n \leq 10\,000 \}$. Then you're looking for the size of the complement of the set $M_2 \cup M_3$. But, as you've observed, these sets overlap. In fact, $$ | M_2 \cup M_3 | = | M_2 | + | M_3 | - | M_2 \cap M_3 |. $$ What about that last term? You want numbers divisible by $2$ and by $3$, namely those divisible by $6$. (In general, a number is divisible by integers $a$ and $b$ if and only if it's divisible by $\operatorname{lcm}(a, b)$.) So, $M_2 \cap M_3 = M_6$, and $$ | M_2 \cup M_3 | = | M_2 | + | M_3 | - | M_6 |. $$ How big are these sets of multiples? As you've implicitly indicated in your question, $$ | M_d | = \biggl\lfloor \frac{10\,000}{d} \biggr\rfloor, $$ where $\lfloor x \rfloor$ is the floor function that rounds numbers down to the greatest integer $m$ satisfying $m \leq x$. Can you put this all together? Try it yourself before revealing the spoiler:

\begin{align} | (M_2 \cup M_3)^{\mathrm{c}} | &= 10\,000 - | M_2 \cup M_3 | \\ &= 10\,000 - \bigl( | M_2 | + | M_3 | - | M_6 | \bigr) \\ &= 10\,000 - \biggl\lfloor \frac{10\,000}{2} \biggr\rfloor - \biggl\lfloor \frac{10\,000}{3} \biggr\rfloor + \biggl\lfloor \frac{10\,000}{6} \biggr\rfloor \\ &= 10\,000 - 5000 - 3333 + 1666 \\ &= 3333\end{align}

Answer 2

How do you figure that "for numbers divisible by $3$, $1/3$ of them are divisible by $2$"? I get $1/2$.

You didn't say but I'm guessing that your "between" is inclusive, so that the number $1$ is included in the count. You could use the in-and-out formula $|A\cup B|=|A|+|B|-|A\cap B|$ but you don't have to.

Observe that, of any six consecutive integers, exactly two of them are divisible neither by $2$ nor by $3$. Now $10000=1666\cdot6+4$, i.e., $1666$ groups of six consecutive integers, plus four at the end. To make things easy look at the four numbers at the little end: $1$, $2$, $3$, $4$. Only one of them (namely $1$) is good, so the final answer is $1666\cdot2+1=\boxed{3333}$. If you're a Big-Endian, of the four numbers at the big end, $9997$, $9998$, $9999$, $10000$, only one of them (namely $9997$) is divisible by neither $2$ nor $3$, so you get the same answer.