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

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 = $\lfloor \frac{19}{2} \rfloor + \lfloor \frac{19}{3} \rfloor + \lfloor \frac{19}{4} \rfloor = 9 + 6 + 4 = 19$

N2 = $\lfloor \frac{19}{6} \rfloor + \lfloor \frac{19}{12} \rfloor + \lfloor \frac{19}{8} \rfloor = 3 + 1 + 2 = 6$

N3 = $\lfloor \frac{19}{24} \rfloor$ = 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?

• Hint: If an integer is divisible by 2 and divisible by 4, is it divisible by 8? – Element118 Oct 26 '15 at 13:22
• Indeed, each (Number of integers which are divisible by $km$) should be replaced by (Number of integers which are divisible by $k$ or by $m$), likewise for (Number of integers which are divisible by $kmn$). – Did Oct 26 '15 at 13:28

So $N_1=19$, $N_2=\lfloor 19/6 \rfloor+\lfloor 19/4 \rfloor+\lfloor 19/12 \rfloor=3+4+1=8$ and $N_3=\lfloor 19/12 \rfloor=1$ which gives you your $12$.