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?

  • 12
    $\begingroup$ How can an integer be divisible by 16 but not by 4? $\endgroup$ May 21 '15 at 20:39
  • $\begingroup$ It's going to take a while to find an integer divisible by $\;16\;$ but not by $\;4\;$ ... $\endgroup$
    – Timbuc
    May 21 '15 at 20:41
  • $\begingroup$ A divisor of a divisor is a divisor. $\endgroup$
    – Bernard
    May 21 '15 at 20:41
  • 1
    $\begingroup$ You mean "divisible by 4, but not by both 3 and 16"? $\endgroup$ May 21 '15 at 20:52
  • 1
    $\begingroup$ @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". $\endgroup$
    – Timbuc
    May 21 '15 at 21:37

$250$ numbers are divisible by $4$. Now use inclusion/exclusion principle:


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).

  • $\begingroup$ @AndréNicolas: I agree, this answer is wrong. I will fix it or delete. Thank you for pointing that out. $\endgroup$ May 21 '15 at 21:25
  • $\begingroup$ You are welcome. $\endgroup$ May 21 '15 at 21:43
  • $\begingroup$ confirmed by awk 'BEGIN{for(i=4; i<=1000; i+=4){if (i%3!=0&&i%16!=0) {print i}}}' | wc -l $\endgroup$ May 21 '15 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.