Let $n$, $p$, $q$ and $r$ be natural numbers. Then

How many numbers between the first $n$ numbers are not divisible neither by $p,\ q$, nor $r$.

There are $\lfloor\frac{n}{pqr}\rfloor$ numbers between the first $n$ that are divisible simultaneaously by $p,\ q$, and $r$.

Then the total number $N^*$ of number not surpassing n and that meet the constraint are:

$$N^* = n - \left\lfloor\frac{n}{pqr}\right\rfloor$$

But since $p$ is not divisible neither by $q$ nor by $r$, and following the same reasoning for $q$ and $r$, we finally have

$$N^* = n - \left\lfloor\frac{n}{pqr}\right\rfloor + 3$$

I'm not sure if it's correct to assume that $p$, $q$ and $r$ are mutually prime numbers


I think that making the assumption of $p , q , r $ being mutually prime is not logical or possible , at least for this problem.

Better would be the following procedure:

First we note that the number of numbers, (say P ) that are divisible by $p$ at least and are lying between $1$ and $n $ is given by $\lfloor \frac {n}{p}\rfloor$.

Similarly, the number of numbers, (say Q and R ) that are divisible respectively by $q$ and $r$ at least and are lying between $1$ and $n $ are respectively given by $\lfloor \frac {n}{q}\rfloor$ and $\lfloor \frac {n}{r}\rfloor$.

So the total number of numbers (say N) not divisible by $p , q , r $ simultaneously is given by $n-\left(\lfloor \frac {n}{p}\rfloor+\lfloor \frac {n}{q}\rfloor+\lfloor \frac {n}{r}\rfloor\right)$

But each of P,Q,R contain some numbers in common, in other words, their multiples. And they have been subtracted in excess from N. So we need to add them.

Hence the number N obtained earlier now becomes $n-\left(\lfloor \frac {n}{p}\rfloor+\lfloor \frac {n}{q}\rfloor+\lfloor \frac {n}{r}\rfloor\right)+\left(\lfloor \frac {n}{pq}\rfloor+\lfloor \frac {n}{qr}\rfloor+\lfloor \frac {n}{rp}\rfloor\right)$

Still, N contains now, one set of extra multiples of $pqr $. So we will subtract that from N.

Thus the final answer is:

$\text{N}=n-\left(\lfloor \frac {n}{p}\rfloor+\lfloor \frac {n}{q}\rfloor+\lfloor \frac {n}{r}\rfloor\right)+\left(\lfloor \frac {n}{pq}\rfloor+\lfloor \frac {n}{qr}\rfloor+\lfloor \frac {n}{rp}\rfloor\right)-\lfloor \frac {n}{pqr}\rfloor$

Hope this helps you.


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.