Results 1 to 5 of 5

Math Help - set

  1. #1
    Mac
    Mac is offline
    Newbie
    Joined
    Jan 2008
    Posts
    2

    set

    If there is a set {1,2,3,...,1000} How many numbers are left if all multiples of 2 3 5 7 are crossed out.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by Mac View Post
    If there is a set {1,2,3,...,1000} How many numbers are left if all multiples of 2 3 5 7 are crossed out.
    Looks to me you can't avoid using a sieve algorithm .....
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Mac
    Mac is offline
    Newbie
    Joined
    Jan 2008
    Posts
    2
    thanks i have done this by exclusion and inclusion principle.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    I'd like to see the solution to this. I have a solution in my head, but it's much too messy and not very efficient. I'm not too familiar with the inclusion-exclusion principle, so if someone could "baby-talk" their way through it, that would be great
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Jhevon View Post
    I'd like to see the solution to this. I have a solution in my head, but it's much too messy and not very efficient. I'm not too familiar with the inclusion-exclusion principle, so if someone could "baby-talk" their way through it, that would be great
    Notation: a|b reads " a divides b"

    Let S = \{1,2,...,1000\}
    Let A = \{ x \in S : 2|x \}
    Let B = \{ x \in S : 3| x\}
    Let C = \{x \in S : 5|x\}
    Let D = \{ x \in S : 7|x\}.

    Now,
    |A\cup B \cup C \cup D| = |A|+|B|+|C|+|D| - |A\cap B| - |A\cap C| - |A\cap D| - |B\cap C| - |B\cap D| - |C\cap D| +|A\cap B\cap C|+|A\cap B\cap D|+|A\cap C \cap D|+|B\cap C\cap D| - |A\cap B\cap C\cap D|

    Now,
    |A| = 500
    |B|= 333
    |C| = 200
    |D|=142

    When you reach the mixed ones it is easy. Because \gcd between any two of 2,3,5,7 is =1 it means that, for example, A\cap B = \{ x\in S : 6 | x\} and A\cap B\cap C = \{ x\in S : 30|x\}. And so on.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum