<s>[INST] 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?
 [/INST] When performing IE with non-coprime elements, you need to use the LCM function.
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$.
</s>