# Integers divisible by 4 but not by 3 and 16

For $n \leq 1000$ I am interested in the integers who are divisible by 4 but not by 3 and 16. Say $a_i$ is the property that an integer is divisible by $i$. Inclusion-Exclusion gives us: \begin{align} N(a_{3}'a_{4}a_{16}') = N - N(a_3) - N(a_4') - N(a_{16}) + N(a_3a_4') + N(a_3a_{16}) + N(a_4'a_{16}) - N(a_{3}'a_{4}a_{16}') \end{align} I can determine those first 4 terms correctly:

• N = 1000

• $N(a_3)= \lfloor \frac{1000}{3} \rfloor = 333$

• $N(a_4')= 1000 - \lfloor \frac{1000}{4} \rfloor = 750$

• $N(a_{16})= \lfloor \frac{1000}{16} \rfloor = 62$

Now it is becoming harder to working things out. We can say for $N(a_3a_4')$ that those are all the numbers that are divisible by 3 but not by 4. We can again apply inclusion-exlusion on this term but it don't seem to help. How can I work this out?

• How can an integer be divisible by 16 but not by 4? May 21 '15 at 20:39
• It's going to take a while to find an integer divisible by $\;16\;$ but not by $\;4\;$ ... May 21 '15 at 20:41
• A divisor of a divisor is a divisor. May 21 '15 at 20:41
• You mean "divisible by 4, but not by both 3 and 16"? May 21 '15 at 20:52
• @MarkBennet Well, when I'll believe in some infinity then I'll be able, perhaps, to respond you. In the meantime I accept infinity as a definite point in some contexts (compactification, elliptic curves with projective geometry, etc.) , very different from usual numbers and thus with no parallel notion of "divisibility". May 21 '15 at 21:37

$250$ numbers are divisible by $4$. Now use inclusion/exclusion principle:
$$250-\left\lfloor\frac{250}{3}\right\rfloor-\left\lfloor\frac{250}{4}\right\rfloor+\left\lfloor\frac{250}{3\times4}\right\rfloor=125$$
Please note that we use $4$ instead of $16$, because those $250$ numbers are not consecutive - they already contain only multiples of $4$, so we need to exclude only those that are multiples of yet "another $4$" (the credit for this fix goes to @AndréNicolas, as implied in the comment below).