How many numbers in between $1$ and $250$ are not divisible by $2, 3, 5$ or $7$? Using the Inclusion Exclusion Principle, I got the answer to be $57$ (i.e. $250-193$), but I'm worried I might have screwed up the arithmetic. Is there a quick and easy way to check whether long calculations like these are right?
[Math] How many numbers in between $1$ and $250$ are not divisible by $2, 3, 5$ or $7$
combinatoricsdiscrete mathematicsdivisibilityelementary-set-theoryinclusion-exclusion
Related Solutions
If $a$ and $b$ are very large numbers, then you can use the following. I will assume that the $a_i$'s are relatively prime (to simplify).
Let $c=\prod_{i=1}^Na_i$.
Then, the number of integers less than $c$ which are divisible by $a_1$ is $\prod_{i=2}^Na_i$, the number of integers less than $c$ which are divisible by $a_1$ and $a_2$ is $\prod_{i=3}^Na_i$.
In general, using the inclusion/exclusion principle, we know that the number of integers relatively prime to $a_1,\cdots,a_n$ is given by (where $S=\{1,\cdots,N\}$)
$$ \prod_{i=1}^Na_i-\sum_{A\subseteq S,|A|=|S|-1}\prod_{i\in S}a_i+\sum_{A\subseteq S,|A|=|S|-2}\prod_{i\in S}a_i-\sum_{A\subseteq S,|A|=|S|-3}\prod_{i\in S}a_i+\cdots+(-1)^N $$
These are the coefficients of the polynomial $\prod(a_i-x)$. So, then, we can calculate the number of integers less than or equal to $c$ relatively prime to the $a_i$'s by substituting $1$ for $x$ and multiplying which takes $O(N)$.
In fact, any sequence of integers of length $c$ will have exactly this many integers relatively prime to the $a_i$'s. So, you could calculate the number of integers less than $m$ which are relatively prime to the $a_i$'s where $1\leq m\leq c\leq 10^{360}$ and break up the interval between $b$ and $a$ into blocks of size $c$ and use a table to look up the rest.
This can give an algorithm that is around $O(N)$ (around because I'm ignoring bit complexity of multiplication) - but the constant is HUGE (at least $10^{360}$).
Your answer is incorrect. While it is true that there are positive odd integers less than or equal to $200$, what you have actually calculated with the expression $$\left\lfloor \frac{200}{2} \right\rfloor$$ is the number of even integers less than or equal to $200$. It just so happens that $200 - 100 = 100$. Similarly, there are $$\left\lfloor \frac{200}{2 \cdot 3} \right\rfloor = 33$$ positive integers less than or equal to $200$ that are divisible by both $2$ and $3$, $$\left\lfloor \frac{200}{2 \cdot 5} \right\rfloor = 20$$ positive integers less than or equal to $200$ that are divisible by both $2$ and $5$, and $$\left\lfloor \frac{200}{2 \cdot 3 \cdot 5} \right\rfloor = 6$$ positive integers less than or equal to $200$ that are divisible by $2$, $3$, and $5$.
However, we can work with these numbers.
Let $A$ be the set of positive odd integers less than or equal to $200$ which are odd; let $B$ be the set of positive integers less than or equal to $200$ which are multiples of $3$; let $C$ be the set of positive integers less than or equal to $200$ which are multiples of $5$. Then \begin{align*} |A| & = 200 - \left\lfloor \frac{200}{2} \right\rfloor = 100\\ |B| & = \left\lfloor \frac{200}{3} \right\rfloor = 66\\ |C| & = \left\lfloor \frac{200}{5} \right\rfloor = 40\\ |A \cap B| & = 66 - \left\lfloor \frac{200}{2 \cdot 3} \right\rfloor = 66 - 33 = 33\\ |A \cap C| & = 40 - \left\lfloor \frac{200}{2 \cdot 5} \right\rfloor = 40 - 20 = 20\\ |B \cap C| & = \left\lfloor \frac{200}{3 \cdot 5} \right\rfloor = 13\\ |A \cap B \cap C| & = 13 - \left\lfloor \frac{200}{2 \cdot 3 \cdot 5} \right\rfloor = 7 \end{align*} where we obtain $|A \cap B|$ by subtracting the number of even multiples of $3$ less than or equal to $200$ from the number of positive integer multiples of $3$ which are at most $200$, $|A \cap C|$ by subtracting the number of even multiples of $5$ less than or equal to $200$ from the number of positive integer multiples of $5$ which are at most $200$, and $|A \cap B \cap C|$ by subtracting the number of even multiples of $3$ and $5$ less than or equal to $200$ from the number of positive integer multiples of $3$ and $5$ less than or equal to $200$.
Hence, by the Inclusion-Exclusion Principle, the number of positive integers less than or equal to $200$ which are odd or divisible by $3$ or divisible by $5$ is $$100 + 66 + 40 - 33 - 20 - 13 + 7 = 147$$
Best Answer
I will first consider all integers up to $210$, as it is the L.C.M. of $2$, $3$, $5$ and $7$. The number of integers from $1$ to $210$ which are not divisible by $2$, $3$, $5$ or $7$ is
$$210-\frac{210}{2}-\frac{210}{3}-\frac{210}{5}-\frac{210}{7}+\frac{210}{6}+\frac{210}{10}+\frac{210}{14}+\frac{210}{15}+\frac{210}{21}+\frac{210}{35}-\frac{210}{30}-\frac{210}{42}-\frac{210}{70}-\frac{210}{105}+\frac{210}{210}$$
which is equal to
$$210\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{7}\right)=48$$
The integers from $211$ to $250$ can be replaced by $1$ to $40$. I prefer to simply list out all integers satisfying the conditions: $1$, $11$, $13$, $17$, $19$, $23$, $29$, $31$, $37$.
So, there are $48+9=57$ such integers.