How many numbers between 1 and 1000 are divisible by 2, 3, 5 or 7?

Question

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.

Answer 1

As the phrasing of the question goes, you require numbers between 1 and 1000, divisible by 2, 3, 5, AND 7, which means divisible by 2*3*5*7=210. Hence your answer is 4. (210, 420, 630, and 840)

Answer 2

I checked it with brute force method. Your result is correct: 772.

var result = [];

for (var i = 0; i <= 1000; ++i) {
 result.push(false);
}

var numbers = [2, 3, 5, 7];

for (var id = 0; id < numbers.length; ++id) {
 var number = numbers[id];
 for (var i = 1; i <= 1000; ++i) {
   if (i % number == 0) {
    result[i] = true;
   }
 }
 }

var counter = 0;
for (var i = 1; i <= 1000; ++i) {
 if (result[i]) {
  ++counter;
 }
}
console.log(counter);

Answer 3

Your solution is correct (or, at least, your result matches mine). Huzzah!

I'm not sure that my approach is much different or more elegant, but it is (I think) a very moderate improvement on the notation: For any natural number $n$, let $a_n$ denote the number of natural numbers between 1 and 1000 (inclusive) which are divisible by $n$. Observe that $$ a_n = \left\lfloor \frac{1000}{n} \right\rfloor. $$ Since each of the factors that we are interested in is prime, we can apply a fairly straight-forward inclusion-exclusion argument: we count how many numbers are divisible by just one of our four prime numbers, then subtract off those that are divisible by exactly two (since they have been double counted), add back those that are divisible by exactly three, and finally subtract off those that are divisible by all four. In the notation above, this is \begin{align} & \underbrace{\left(a_2 + a_3 + a_5 + a_7\right)}_{\text{one factor}} - \underbrace{\left(a_6 + a_{10} + a_{14} + a_{15} + a_{21} + a_{35}\right)}_{\text{two factors}} + \underbrace{\left(a_{30} + a_{42} + a_{70} + a_{105}\right)}_{\text{three factors}} - a_{210} \\ &\quad= (500 + 333 + 200 + 142) - (166 + 100 + 71 + 66 + 47 + 28) + (33 + 23 + 14 + 9) - 4 \\ &\quad= 1175 - 478 + 79 - 4 \\ &\quad= 772. \end{align}

---

Alternatively, if you want to be really clever with notation, we could write \begin{align} &\sum_{j \in\{2,3,5,7\}} \left\lfloor \frac{1000}{j} \right\rfloor - \sum_{\substack{j,k\in\{2,3,5,7\}\\ j < k}} \left\lfloor \frac{1000}{jk} \right\rfloor + \sum_{\substack{j,k,\ell \in\{2,3,5,7\}\\ j < k < \ell}} \left\lfloor \frac{1000}{jk\ell} \right\rfloor - \sum_{\substack{j,k,\ell,m \in\{2,3,5,7\}\\ j < k < \ell < m}} \left\lfloor \frac{1000}{jk\ell m} \right\rfloor. \end{align} We could use this same idea to generalize to any number of prime factors. Composite factors would require a little bit of extra care. Also, note that this is exactly what is above, written in a somewhat annoying manner (in particular, the last sum is a really, really complicated way of writing $\left\lfloor \frac{1000}{2\cdot 3\cdot 5\cdot 7} \right\rfloor$).

---

Even more pathologically, at the suggestion of Dan Uznanski, we could write $$ \sum_{S \in \mathscr{P}(\{2,3,5,7\}) \setminus \emptyset} (-1)^{|S|+1} \left\lfloor \frac{1000}{\prod_{s\in S} s} \right\rfloor, $$ where $\mathscr{P}(S)$ denotes the powerset of a set $S$, and $|S|$ is the cardinality of $S$.

Answer 4

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$.

Answer 5

This is correct, and for those who may not see how to approach the problem using the principle of inclusion-exclusion, I will write it out. To find how many numbers in the set $\{1,...,1000\}$ are multiples of $2,3,5,$ or $7$ using the principle of inclusion-exclusion, we define the following sets:

$\overline{C_1} = \{ x : x \in \{1,...,1000\},\: 2 \vert x \}$ (set of numbers divisible by 2)

$\overline{C_2} = \{ x : x\in \{1,...,1000\},\: 3 \vert x \}$ (set of numbers divisible by 3)

$\overline{C_3} = \{ x : x\in\{1,...,1000\},\: 5 \vert x \}$ (set of numbers divisible by 5)

$\overline{C_4} = \{ x : x\in\{1,...,1000\},\: 7 \vert x \}$ (set of numbers divisible by 7)

So the set of all numbers in the range $[1, 1000]$ divisible by $2,3,5,$ or $7$ is $\overline{C_1} \cup \overline{C_2} \cup \overline{C_3} \cup \overline{C_4}$. We can obtain the size of this set through the principle of inclusion-exclusion:

$|\overline{C_1} \cup \overline{C_2} \cup \overline{C_3} \cup \overline{C_4}| = \displaystyle\sum_{k = 1}^{4} (-1)^{k - 1} \displaystyle\sum_{I \in \binom{\{1, ..., 4\}}{k}} \left\lvert \bigcap_{i \in I} \overline{C_i} \right\rvert$

$= |\overline{C_1}| + |\overline{C_2}| + |\overline{C_3}| + |\overline{C_4}| - |\overline{C_1} \cap \overline{C_2}| - |\overline{C_1} \cap \overline{C_3}| - |\overline{C_1} \cap \overline{C_4}| - |\overline{C_2} \cap \overline{C_3}| - |\overline{C_2} \cap \overline{C_4}| - |\overline{C_3} \cap \overline{C_4}| + |\overline{C_1} \cap \overline{C_2} \cap \overline{C_3}| + |\overline{C_1} \cap \overline{C_2} \cap \overline{C_4}| + |\overline{C_1} \cap \overline{C_3} \cap \overline{C_4}| + |\overline{C_2} \cap \overline{C_3} \cap \overline{C_4}| - |\overline{C_1} \cap \overline{C_2} \cap \overline{C_3} \cap \overline{C_4}|$

Now consider the size of an individual set $\overline{C}_i$. For example, for $\overline{C}_1$, how would we find the size of this set? In other words, how many numbers in the range $[1, 1000]$ are divisible by $2$? Well, we can first consider how we can sequentially construct all the multiples of $2$ less than $1000$:

$$(2 + (2 \cdot 0)) + (2 + (2 \cdot 1)) + (2 + (2 \cdot 2)) + \cdots + (2 + (2 \cdot (n - 1))) \leq 1000$$

So what we want is that value of $n$ (i.e. how many times $2$ goes into $1000$), which is just $\dfrac{1000}{2} = 500$. But what if we have a number like $3$ that doesn't divide $1000$? Then we'll need to floor (round down towards 0) the result of $\dfrac{1000}{3} = 333.\overline{33}$ because $333 \cdot 3 = 999$ is the greatest multiple of 3 less than $1000$. So generally, to find the number of multiples of some natural number $n$ less than another natural number $m$, we compute $\left\lfloor \dfrac{m}{n} \right\rfloor$. The same logic will apply when finding the size of an arbitrary intersection $$\overline{C}_{i_1} \cap \cdots \cap \overline{C}_{i_k} \: (i_j \in \{1,...,4\}, j \in \{1,...,k\}, k \leq n)$$

For example, if we have the intersection $\overline{C}_{2} \cap \overline{C}_{3} \cap \overline{C}_4$, we need the size of the set that consists of all multiples of $3 \cdot 5 \cdot 7$ less than $1000$, which is $\left\lfloor \dfrac{1000}{3 \cdot 5 \cdot 7} \right\rfloor$. So if we have $n$ natural numbers and we want to find all natural numbers less than $1000$ that are divisible by these $n$ natural numbers, we compute $\left\lfloor \dfrac{1000}{i_1 \cdot i_2 \cdots i_n} \right\rfloor$. With this in mind, we can compute $|\overline{C_1} \cup \overline{C_2} \cup \overline{C_3} \cup \overline{C_4}|$ by rewriting our formula for the principle of inclusion-exclusion with our knowledge of the size of the arbitrary intersections between the previously defined sets:

$|\overline{C_1} \cup \overline{C_2} \cup \overline{C_3} \cup \overline{C_4}| = \displaystyle\sum_{k = 1}^{4} (-1)^{k - 1} \displaystyle\sum_{I \in \binom{\{2, 3, 5, 7\}}{k}} \left\lfloor 1000 \cdot \prod_{i \in I} \dfrac{1}{i} \right\rfloor = $

$\left\lfloor \dfrac{1000}{2} \right\rfloor + \left\lfloor \dfrac{1000}{3} \right\rfloor + \left\lfloor \dfrac{1000}{5} \right\rfloor + \left\lfloor \dfrac{1000}{7} \right\rfloor - \left\lfloor \dfrac{1000}{2 \cdot 3} \right\rfloor - \left\lfloor \dfrac{1000}{2 \cdot 5} \right\rfloor - \left\lfloor \dfrac{1000}{2\cdot 7} \right\rfloor - \left\lfloor \dfrac{1000}{3 \cdot 5} \right\rfloor - \left\lfloor \dfrac{1000}{3 \cdot 7} \right\rfloor - \left\lfloor \dfrac{1000}{5 \cdot 7} \right\rfloor + \left\lfloor \dfrac{1000}{2 \cdot 3 \cdot 5} \right\rfloor + \left\lfloor \dfrac{1000}{2 \cdot 3 \cdot 7} \right\rfloor + \left\lfloor \dfrac{1000}{2 \cdot 5 \cdot 7} \right\rfloor + \left\lfloor \dfrac{1000}{3 \cdot 5 \cdot 7} \right\rfloor - \left\lfloor \dfrac{1000}{2 \cdot 3 \cdot 5 \cdot 7} \right\rfloor$

$= 500 + 333 + 200 + 142 - 166 - 100 - 71 - 66 - 47 - 28 + 33 + 23 + 14 + 9 - 4 = 772$.