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 $m$ to $n$ $(m which are divisible by any of $a_1,a_2,\ldots,a_n$ using this formula:

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

$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 -$ $\cdots$ $+ (-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 $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 $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, $4,9,14,19,24,$ you can throw the $24$ away; it is enough just to count the multiples of $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 $\gcd(4,14)\ne1$ we should be considering $\mathrm{lcm}(4,14)=28$ instead of $4\cdot14=56.$ Go back to your calculations and replace all instances of $4\cdot14$ with $28$ – e.g. instead of $\left\lfloor \frac{901}{4\cdot14\cdot19} \right\rfloor$ compute $\left\lfloor \frac{901}{28\cdot19} \right\rfloor.$

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

PPS: The amended formula should be as follows:

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

Thanks a lot