4
$\begingroup$

I need to find the number of natural numbers between 1 and 1000 that are divisible by 3, 5 or 7.

I know that given a set of numbers, 1 ... n, the number of numbers divisible by d is given by $\lfloor \frac{n}{d} \rfloor$

So if we let $A$ be the set of numbers divisible by 3, $B$ be the set of numbers divisible by 5 and $C$ be the set of numbers divisible by 7, then the size of the union of those sets is going to be the number required.

However, to work out $A \cup B \cup C$, I need to know $A \cap B$ (and $A \cap C$ etc).

My only thought was that to work out $A \cap B$, I could use $\lfloor \frac{1000}{3 \times 5} \rfloor$, but I am unsure if this misses out some numbers. Is that the correct way to do it or not? If no, can anyone suggest the correct way.

$\endgroup$
7
$\begingroup$

In general, you have to use $\left\lfloor\frac{1000}{[a,b]}\right\rfloor$, where $[a,b]$ is the least common multiple of $a$ and $b$.

$\endgroup$
5
$\begingroup$

That's right. A number is divisible by 3 and 5 if and only if it is divisible by 15.

$\endgroup$
  • $\begingroup$ But since 3, 5, and 7, the OP does present the correct way to do it in his situation. $\endgroup$ – scott Jul 8 '16 at 19:35
  • $\begingroup$ @scott: The question was about the size of the set $A \cap B$. $\endgroup$ – Hans Lundmark Jul 9 '16 at 8:50
1
$\begingroup$

divisibility by 3 or 5 or by both means: N(3 or 5)=N(3) + N(5) -N(3 and 5) N(3 and 5) bcoz remove all common from nos. divisible by 3 and 5

N(3)=1000/3=333 N(5)=1000/5=200 N(3 and 5)=66 so 333+200-66=467

$\endgroup$
  • $\begingroup$ Welcome to MSE. You may wish to have a look at our tutorial to learn how to typeset math here. Also, why did you choose to answer such an old question? Your answer is hard to read and doesn't add anything to the others already present. (Not to mention that, being one answer already accepted, it is unlikely that other people will see your answer, due to how the site works.) $\endgroup$ – A.P. Apr 16 '15 at 18:16
0
$\begingroup$

You can be sure that it does not miss any number. It comes out as an multiplication because you are looking for the common multiple of 2 prime numbers.

It would be the same for the other intersections that you need. $$(A\cap B), (A \cap B \cap C) $$

$\endgroup$
0
$\begingroup$

1~1000, there are 333 numbers can be divided by 3; there are 200 numbers can be divided by 5; there are 142 numbers can be divided by 7; However there are 66 numbers can be divided by both 3 and 5 (e.g. 15); there are 47 numbers can be divided by both 3 and 7 (e.g. 21); there are 28 numbers can be divided by both 5 and 7 (e.g. 35); Thus: 333+200+142-66-47-28=534 However there are 9 multiples of 105, which have been included in all of above "333, 200, 142, 66, 47, and 28", thus after the subtraction, there is 0 multiple of 105, thus we have to add the number of multiples of 105 to the "534". Therefore, totally there should have 543 numbers between 1~1000 which can be divided by 3, 5, or 7.

$\endgroup$

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.