1. ## cheking no divisiblity

Hi, for a range of integers, how can we know the number of integers in that range(both inclusive) which are NOT divisible by either of numbers in a given set ?
E.g if we have a range 100 to 1000 and the given set of integers is 4,9,14,19,24 then the number of integers in 100 - 1000 (both inclusive) which are NOT divisible by either of the integers in the given set is 543. I tried to solve it using set theory i.e:
let sum = (1000- (1000/4+1000/9+1000/14+1000/19+1000/24)) + (100-(100/4+100/9+100/14+100/19+100/24))
then ans = 1000-100-sum
but am not getting correct answer.
Thanks.

2. ## Re: Checking no divisibility

First, find the number of numbers from $\displaystyle m$ to $\displaystyle n$ $\displaystyle (m<n)$ which are divisible by any of $\displaystyle a_1,a_2,\ldots,a_n$ using this formula:

Let $\displaystyle S_1=\{a_1,a_2,\ldots,a_n\},$ $\displaystyle S_2=$ {product of members of $\displaystyle S_1$ taken 2 at a time}, $\displaystyle S_3=$ {product of members of $\displaystyle S_1$ taken 3 at a time}, …, $\displaystyle S_n=\{a_1a_2\cdots a_n\}.$ Then the number of numbers which are divisible is

$\displaystyle s = \sum_{s\in S_1}\left\lfloor\frac{n-m+1}s\right\rfloor - \sum_{s\in S_2}\left\lfloor\frac{n-m+1}s\right\rfloor + \sum_{s\in S_3}\left\lfloor\frac{n-m+1}s\right\rfloor -$ $\displaystyle \cdots$ $\displaystyle + (-1)^{n+1}\left\lfloor\frac{n-m+1}{a_1a_2\cdots a_n}\right\rfloor$

The number of numbers that are not divisible is then $\displaystyle n-m+1-s.$

3. ## Re: Checking no divisibility

thanks Sylvia, i tried the above method but it doesn't seem to give correct answer . E.g for n = 1000 and m = 100 it gives 508 instead of 543.

4. ## Re: Checking no divisibility

I think I know what's wrong. The formula only works if none of the $\displaystyle a_1,a_2,\ldots,a_n$ is a whole multiple of any other. If one of them is a multiple of another, we can throw away the biggest multiple. In your example, $\displaystyle 4,9,14,19,24,$ you can throw the $\displaystyle 24$ away; it is enough just to count the multiples of $\displaystyle 4.$

5. ## Re: cheking no divisiblity

i think the formula fails again..it gives 530 ..need to add some another term now ?

6. ## Re: Checking no divisibility

Of course. Because $\displaystyle \gcd(4,14)\ne1$ we should be considering $\displaystyle \mathrm{lcm}(4,14)=28$ instead of $\displaystyle 4\cdot14=56.$ Go back to your calculations and replace all instances of $\displaystyle 4\cdot14$ with $\displaystyle 28$ – e.g. instead of $\displaystyle \left\lfloor \frac{901}{4\cdot14\cdot19} \right\rfloor$ compute $\displaystyle \left\lfloor \frac{901}{28\cdot19} \right\rfloor.$

PS: I just did the calculation myself and got $\displaystyle 543$ so the formula should be correct now. Please don't tell me you didn't get $\displaystyle 543$ yourself.

PPS: The amended formula should be as follows:

Let $\displaystyle S_1=\{a_1,a_2,\ldots,a_n\},$ $\displaystyle S_2=$ {lcm of members of $\displaystyle S_1$ taken 2 at a time}, $\displaystyle S_3=$ {lcm of members of $\displaystyle S_1$ taken 3 at a time}, …, $\displaystyle S_n = \{\mathrm{lcm}(a_1a_2\cdots a_n)\}.$ Then compute $\displaystyle s$ as above.

Thanks a lot