Results 1 to 7 of 7

Math Help - 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; April 18th 2012 at 09: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 m to n (m<n) 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.
    Last edited by Sylvia104; April 20th 2012 at 04: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 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.
    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 \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.
    Last edited by Sylvia104; April 21st 2012 at 04: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: March 15th 2010, 10:31 AM
  2. Questions Involving Divisiblity
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 20th 2009, 05:14 AM
  3. Divisiblity Proofs
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 23rd 2009, 11:01 AM

Search Tags


/mathhelpforum @mathhelpforum