find the sum of all numbers not divisible by 2 and 5 in between 1 to 1000
Answers
Answer:
Step-by-step explanation:
This problem is a common application of PIE (principle of inclusion and exclusion).
First let’s decide to count the amount of positive integers less than 10001000 that are divisible by 22, 33, or 55. Notice that this number can be subtracted from 999 in order to get the actual answer to the problem.
For this problem it would follow that to count all integers divisible by 22, 33, or 55, we could count the amount divisible by 22, the amount divisible by 33, and the amount divisible by 55 and add up the three numbers. Notice that this over counts the desired amount.
In order to get around this dilemma, we can instead subtract the one’s divisible by 22 and 33, 33 and 55, and 22 and 55, which were counted twice. One more problem though is that numbers divisible by all three were under counted and need to be added back to the answer.
To show this in a more formal way, let SxSx be the set of numbers below 1000 divisible by xx. Our desired answer is the size of S2∪S3∪S5S2∪S3∪S5. Using the above logic we can calculate this as |S2∪S3∪S5|=|S2|+|S3|+|S5|−|S2∩S3|−|S3∩S5|−|S2∩S5|+|S2∩S3∩S5||S2∪S3∪S5|=|S2|+|S3|+|S5|−|S2∩S3|−|S3∩S5|−|S2∩S5|+|S2∩S3∩S5|.
If you don’t understand basic set notation remember that |S||S| is the size of set SS and ∩∩ is the intersection of two sets (the overlap between both sets) while ∪∪ is the union of two sets (all distinct elements between both sets).
If you are having trouble visualizing PIE, try looking at the Venn diagram above and notice how many times each region of the diagram gets counted in the formula.
Now to the calculation part.
|S2|=⌊9992⌋=499|S2|=⌊9992⌋=499
|S3|=⌊9993⌋=333|S3|=⌊9993⌋=333
|S5|=⌊9995⌋=199|S5|=⌊9995⌋=199
|S2∩S3|=⌊9996⌋=166|S2∩S3|=⌊9996⌋=166
|S2∩S5|=⌊99910⌋=99|S2∩S5|=⌊99910⌋=99
|S3∩S5|=⌊99915⌋=66|S3∩S5|=⌊99915⌋=66
|S2∩S3∩S5|=⌊99930⌋=33|S2∩S3∩S5|=⌊99930⌋=33
Plugging in all these values gives 499+333+199−166−99−66+33=733499+333+199−166−99−66+33=733. Therefore the original answer is 999−733=266999−733=266. Therefore the are 266266 positive integers less than 10001000 that are divisible by none of 22, 33, and 55.