Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number of positive integers that are not divisible by 17

  1. Jun 15, 2010 #1
    Find the number of positive integers in the range of 1976 through 3776 that are not divisible by 17.

    [tex]A=[/tex]{[tex]\mathbb{Z}^+\ \mbox{not divisible by 17}[/tex]}

    Then I am looking for [tex]A^c[/tex]

    I am not sure how to do this though.
     
  2. jcsd
  3. Jun 15, 2010 #2

    Mark44

    Staff: Mentor

    17 | 1989.
    Count the number of integers in [1976, 3776] - there are an odd number of them, and subtract all the numbers that are multiples of 17.
     
  4. Jun 15, 2010 #3
    So if I think of the set of integers as set, I want the card(3776)-card(1976) but I don't understand how to isolate the integers that are divisible by 17.
     
  5. Jun 15, 2010 #4
    Here's a similar example. If I ask you how many multiples of 17 are there between 2*17 and 5*17 inclusive, what would you say?
     
  6. Jun 15, 2010 #5
    [tex]\left \lfloor \frac{85}{17} \right \rfloor-\left \lfloor \frac{34}{17} \right \rfloor + 1[/tex]
     
  7. Jun 15, 2010 #6

    Mark44

    Staff: Mentor

    How many integers are in the interval [1976, 3776]? In the interval [a, b], with a and b integers and b > a, there are b - a + 1 integers.

    The first integer in your interval that is divisible by 17 is 1789. What's the next? And the next? Keep doing that until you run past the end of the interval, and keep track of how many you have found.

    That's sort of a "brute force" way of doing it. There might be a more elegant way, but this should be pretty quick.

    BTW, what is card(3776) supposed to mean? You can talk about the cardinality of a set, but it doesn't seem very useful to talk about the cardinality of a single number.
     
  8. Jun 15, 2010 #7

    Mark44

    Staff: Mentor

    Simplified, this is what?
     
  9. Jun 15, 2010 #8
    I didn't feel like labeling a set B and C which would be the number of integers divisible by 17
     
  10. Jun 15, 2010 #9
    That would simply be 4
     
  11. Jun 15, 2010 #10

    Mark44

    Staff: Mentor

    Yes. A simple answer is better than a complicated answer.

    Now extend this idea to find the multiples of 17 in the interval [1976, 3776]. Find the smallest multiple of 17 (1989) and the largest multiple in this interval, and use the same technique you used to get 4.
     
  12. Jun 15, 2010 #11
    [tex]3776-1976+1-\left(\left \lfloor \frac{3776}{17} \right \rfloor - \left \lfloor \frac{1976}{17} \right \rfloor + 1\right)=1694[/tex]

    The answer is supposed to be 1695 though.
     
  13. Jun 15, 2010 #12

    Mark44

    Staff: Mentor

    That's what I get.
     
  14. Jun 15, 2010 #13
    What do you get? 1694 or 1695?
     
  15. Jun 16, 2010 #14

    Mark44

    Staff: Mentor

    1695. I spoke too soon before.

    There are 1801 integers in the interval [1776, 3776], and there are 106 numbers in that intervale that are multiples of 17.
     
  16. Jun 16, 2010 #15
    Well, you shouldn't floor the 3776-one. That would make you over count by one.
    Say we know there are 1801 numbers. We want to know how many are divisible by 17. Take the lowest and highest number:
    1976/17=116.something
    3776/17=222.something'
    this means that the 117th number divisible by 17 is in there, and the 222nd is too. But you floored that 222.something making it 223, which is not (!) there, making you over count by one.
    So we get 222-116=106 numbers divisible by 17. Subtract this from the number of numbers (tihi) and get 1801-106=1695
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook