1
$\begingroup$

I need to find the number of $75\leq n\leq 300$ not divisible by any of $9,12,15$.

I thought about to solve this for $1\leq n\leq 300$ and $1\leq n\leq 74$ and then subtract. For each of them I thought to use inclusion-exclusion. I just want to check whether I'm right.

For the first problem, the answer is:

$300-\left(\left\lfloor\frac{300}{9}\right\rfloor+\left\lfloor\frac{300}{12}\right\rfloor+\left\lfloor\frac{300}{15}\right\rfloor-\left\lfloor\frac{300}{\operatorname{lcm}(9,12)}\right\rfloor-\left\lfloor\frac{300}{\operatorname{lcm}(9,15)}\right\rfloor-\left\lfloor\frac{300}{\operatorname{lcm}(12,15)}\right\rfloor+\left\lfloor\frac{300}{\operatorname{lcm}(9,12,15)}\right\rfloor\right)$

and for the second the same expression with $74$ replacing each $300$. Finally, subtract them. Is this correct?

$\endgroup$
  • 1
    $\begingroup$ print sum([0 not in [n%9,n%12,n%15] for n in range(75,301)]) gives 180. $\endgroup$ – barak manos Sep 12 '16 at 9:02
  • $\begingroup$ what kind of code is this? $\endgroup$ – Dr. Sonnhard Graubner Sep 12 '16 at 9:07
  • $\begingroup$ @Dr.SonnhardGraubner: Python. $\endgroup$ – barak manos Sep 12 '16 at 9:10
1
$\begingroup$

Let $f(n)$ denote the amount of integers in the range $[1,n]$ not divisible by $9$ nor $12$ nor $15$:

$f(n)=n-\left\lfloor\frac{n}{9}\right\rfloor-\left\lfloor\frac{n}{12}\right\rfloor-\left\lfloor\frac{n}{15}\right\rfloor+\left\lfloor\frac{n}{lcm(9,12)}\right\rfloor+\left\lfloor\frac{n}{lcm(9,15)}\right\rfloor+\left\lfloor\frac{n}{lcm(12,15)}\right\rfloor-\left\lfloor\frac{n}{lcm(9,12,15)}\right\rfloor$

We can simplify it as $f(n)=n-\left\lfloor\frac{n}{9}\right\rfloor-\left\lfloor\frac{n}{12}\right\rfloor-\left\lfloor\frac{n}{15}\right\rfloor+\left\lfloor\frac{n}{36}\right\rfloor+\left\lfloor\frac{n}{45}\right\rfloor+\left\lfloor\frac{n}{60}\right\rfloor-\left\lfloor\frac{n}{180}\right\rfloor$


And the answer to your question is $f(300)-f(74)$:

  • $f(300)=240$
  • $f(74)=60$

Hence the amount of such integers is $240-60=180$.

Python verification: print sum([0 not in [n%9,n%12,n%15] for n in range(75,301)]).

$\endgroup$

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.