Finding number of integers divisible by 2, 3 or 4 using inclusion-exclusion principle.

Revision en1, by gagantheroyal, 2015-10-26 16:04:18

I want to find number of integers from 1 to 19 (both included) which are divisible by 2 or 3 or 4. Lets denote it by N. So counting and enumerating them gives N = 12. Integers are 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16 and 18.

I thought of applying inclusion-exclusion principle for finding N. Here is how I proceeded:

Lets denote the followings:

N1 = (Number of integers which are divisible by 2) + (Number of integers which are divisible by 3) + (Number of integers which are divisible by 4)

N2 = (Number of integers which are divisible by 2*3 = 6) + (Number of integers which are divisible by 3*4 = 12) + (Number of integers which are divisible by 2*4 = 8)

N3 = (Number of integers which are divisible by 2*3*4 = 24)

Then using inclusion-exclusion principle we have: N = N1 — N2 + N3

Finding N1, N2 and N3 (denoting Greatest Integer Function using floor function):

N1 = floor(19 / 2) + floor(19 / 3) + floor(19 / 4) = 9 + 6 + 4 = 19

N2 = floor(19 / 6) + floor(19 / 12) + floor(19 / 8) = 3 + 1 + 2 = 6

N3 = floor(19 / 24) = 0

Therefore, N = N1 — N2 + N3 = 19 — 6 + 0 = 13.

From here, I am getting N = 13 which is wrong as I counted them manually above (N = 12).

Can anyone point out the mistake I am making here and suggest the correct way of doing this using inclusion-exclusion principle?

Tags inclusion-exclusion, divisiblity

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English gagantheroyal 2015-10-26 16:04:18 1478 Initial revision (published)