The Student Room Group

No. of integers < 6000, not divisible by 2, 3 or 5

I've got:

Divisible by... 2, 3, 5, 2 and 3, 2 and 5, 3 and 5
No of integers 3000, 2000, 1200, 1000, 600, 400

And then it's
6000
- 3000 (integers divisible by 2)
- 2000 + 1000 (integers divisible by 3 but not 2)
- 1200 + 600 + 400 (integers divisible by 5 alone)

= 1800

Is this right? Can anyone think of any better ways of doing it?
Reply 1
e-unit
I've got:

Divisible by... 2, 3, 5, 2 and 3, 2 and 5, 3 and 5
No of integers 3000, 2000, 1200, 1000, 600, 400

And then it's
6000
- 3000 (integers divisible by 2)
- 2000 + 1000 (integers divisible by 3 but not 2)
- 1200 + 600 + 400 (integers divisible by 5 alone)

= 1800

Is this right? Can anyone think of any better ways of doing it?


It's an inclusion-exclusion formula job

|AUBUC| = |A|+|B|+|C|-|AnB|-|BnC|-|CnA| + |AnBnC|

Let A be evens, B multiples of 3 and C multiples of 5.

Those divisible by one or more
= 3000 + 2000 + 1200 - 1000 - 400 - 600 + 200
= 4400

Answer = 1600
Reply 2
6000 - 3000 - 2000 - 1200 + 1000 + 400 + 600 - 30 = 1770
Reply 3
Neapolitan
It's an inclusion-exclusion formula job

|AUBUC| = |A|+|B|+|C|-|AnB|-|BnC|-|CnA| + |AnBnC|

Let A be evens, B multiples of 3 and C multiples of 5.

Those divisible by one or more
= 3000 + 2000 + 1200 - 1000 - 400 - 600 + 200
= 4400

Answer = 1600

why + 200? shouldnt it be (6000/(2×3×5)) = 30?
so the final answer is 1770?

i.e

6000 - 3000 - 2000 - 1200 + 1000 + 400 + 600 - 30 = 1770
Reply 4
6000 - 3000 - 2000 - 1200 + 1000 + 400 + 600 - 200 = 1600
Reply 5
hello e-unit.

For this question I think you need to use the 'sum rule'.
Call A the set of integers <6000 divisible by 2.
Call B the set of integers <6000 divisible by 3
Call C the set of integers <6000 divisible by 5 .

By the sum rule, the number of integers <6000 which ARE divisible by 2,3 or 5 is given by No. of integers in A + No of integers in B + No of integers in C
- No of integers in A intersect B - No of integers in A intersect C - No of integers in B intersect C + No of integers in A intersect B intersect C

= 3000 + 2000 + 1200 - 1000 - 600 - 400 + 300
= 4500.

So that the number of integers <6000 not divisible by 2,3 or 5 is 6000 - 4500 = 1500.

I think this is right and I'm pretty sure your method is the quickest way to go about answering this question.
Reply 6
beast
hello e-unit.

For this question I think you need to use the 'sum rule'.
Call A the set of integers <6000 divisible by 2.
Call B the set of integers <6000 divisible by 3
Call C the set of integers <6000 divisible by 5 .

By the sum rule, the number of integers <6000 which ARE divisible by 2,3 or 5 is given by No. of integers in A + No of integers in B + No of integers in C
- No of integers in A intersect B - No of integers in A intersect C - No of integers in B intersect C + No of integers in A intersect B intersect C

= 3000 + 2000 + 1200 - 1000 - 600 - 400 + 200
= 4400.

So that the number of integers <6000 not divisible by 2,3 or 5 is 6000 - 4400 = 1600. Sorry, AnBnC should have been 200 not 300!!

I think this is right and I'm pretty sure your method is the quickest way to go about answering this question.
Cheers mate.
Reply 7
Alternatively:

1/2 the numbers are not divisible by 2, 2/3 of the numbers aren't divisible by 3 and 4/5 of the numbers aren't divisible by 5. So:

Answer = 1/2 * 2/3 * 4/5 * 6000 = 1600

A little quicker without the need for inclusion-exclusion.
Reply 8
Wrangler's method is impressive! I've never seen this kind of question dealt with in such a way! So that's probably the quickest way!!
Reply 9
beast
Wrangler's method is impressive!

Much appreciated! :smile:
although needs a bit if adjustment on the result when n is not a multiple of the factors?
Reply 11
pure6gapper
although needs a bit if adjustment on the result when n is not a multiple of the factors?
Yup. But he didn't claim it was a general result, and in this case it works just fine!
Reply 12
Cexy
Yup. But he didn't claim it was a general result, and in this case it works just fine!

Is there a general result? Can you explain why it only works because n is a multiple of the factors?
Reply 13
e-unit
Is there a general result? Can you explain why it only works because n is a multiple of the factors?

1st general problem:
How many natural numbers is less than positive number n and not divisible by 2, 3, and 5

2nd general problem:
How many natural numbers is less than positive number n and not divisible by a, b, and c where each pair of (a, b and c) is coprime

3rd general problem:
How many natural integer numbers less than positive number n and not divisible by a1, a2,..., ak where each pair of them is coprime

Edit: just consider natural numbers :redface: