3
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ It should be “2 , 3, 5 or 7”. $\endgroup$ – user371838 Jan 1 '18 at 13:01
  • $\begingroup$ I am afraid there may be an elegant solution if you insist with and, and not so, if it is or. $\endgroup$ – user371838 Jan 1 '18 at 13:02
  • $\begingroup$ It should be or. My apologies $\endgroup$ – Moshe King Jan 1 '18 at 13:03
  • $\begingroup$ I haven't checked the numbers, but your inclusion-exclusion argument should work. $\endgroup$ – Paul Aljabar Jan 1 '18 at 13:10
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Note that this doesn't work when any of the numbers we're testing divisibility for are composite. $\endgroup$ – Dan Uznanski Jan 1 '18 at 14:34
  • $\begingroup$ how would you change it to work for composite numbers? $\endgroup$ – oliver Apr 27 '20 at 13:51
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ $$\sum_{S \in P(\{2,3,5,7\})}(-1)^{|S|+1}\left\lfloor\frac{1000}{\prod_{x\in S}x}\right\rfloor$$ $\endgroup$ – Dan Uznanski Jan 2 '18 at 5:20
  • $\begingroup$ @DanUznanski Ha! I like it! $\endgroup$ – Xander Henderson Jan 2 '18 at 15:22
  • $\begingroup$ I messed it up though, you have to exclude the empty set from the sum. $\endgroup$ – Dan Uznanski Jan 2 '18 at 15:23
0
$\begingroup$

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)

$\endgroup$
5
  • $\begingroup$ It should be or. My apologies $\endgroup$ – Moshe King Jan 1 '18 at 13:04
  • $\begingroup$ @GADI Your solution is the best. No need to worry. $\endgroup$ – user371838 Jan 1 '18 at 13:04
  • $\begingroup$ It's good practice to clarify what the OP says if you're not sure - this will save you from writing your answer all over again. No need to worry - no one has written a good answer yet. $\endgroup$ – Toby Mak Jan 1 '18 at 13:04
  • $\begingroup$ Thank you @Rohan Did you get the same result? $\endgroup$ – Moshe King Jan 1 '18 at 13:08
  • $\begingroup$ @GADI Yes, the same result.. $\endgroup$ – user371838 Jan 1 '18 at 13:12
0
$\begingroup$

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);
$\endgroup$
3
  • $\begingroup$ Welcome to MSE. Your answer can hardly be described as a “different, more elegant approach”. $\endgroup$ – José Carlos Santos Jan 1 '18 at 13:19
  • $\begingroup$ @JoséCarlosSantos This was verification, however. $\endgroup$ – DynamoBlaze Jan 1 '18 at 13:22
  • $\begingroup$ @piotrl Adding to this, 'I checked it with brute force method' is definitely not a 'different, more elegant approach'. $\endgroup$ – Toby Mak Jan 1 '18 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.