Number of $75\leq n\leq 300$ not divisible by any of $9,12,15$ - check work

Question

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?

Answer 1

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