Results 1 to 7 of 7

Thread: cheking no divisiblity

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    95

    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.
    Last edited by pranay; Apr 18th 2012 at 08:16 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    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.$
    Last edited by Sylvia104; Apr 20th 2012 at 03:40 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2010
    Posts
    95

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    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.$
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2010
    Posts
    95

    Re: cheking no divisiblity

    i think the formula fails again..it gives 530 ..need to add some another term now ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    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.
    Last edited by Sylvia104; Apr 21st 2012 at 03:29 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Nov 2010
    Posts
    95

    Re: cheking no divisiblity

    Thanks a lot
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisiblity test for 3
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 15th 2010, 09:31 AM
  2. Questions Involving Divisiblity
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Aug 20th 2009, 04:14 AM
  3. Divisiblity Proofs
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Apr 23rd 2009, 10:01 AM

Search Tags


/mathhelpforum @mathhelpforum