Number of positive integers that are not divisible by 17

1. Jun 15, 2010

Dustinsfl

Find the number of positive integers in the range of 1976 through 3776 that are not divisible by 17.

$$A=$${$$\mathbb{Z}^+\ \mbox{not divisible by 17}$$}

Then I am looking for $$A^c$$

I am not sure how to do this though.

2. Jun 15, 2010

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.

3. Jun 15, 2010

Dustinsfl

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.

4. Jun 15, 2010

Tedjn

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?

5. Jun 15, 2010

Dustinsfl

$$\left \lfloor \frac{85}{17} \right \rfloor-\left \lfloor \frac{34}{17} \right \rfloor + 1$$

6. Jun 15, 2010

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.

7. Jun 15, 2010

Staff: Mentor

Simplified, this is what?

8. Jun 15, 2010

Dustinsfl

I didn't feel like labeling a set B and C which would be the number of integers divisible by 17

9. Jun 15, 2010

Dustinsfl

That would simply be 4

10. Jun 15, 2010

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.

11. Jun 15, 2010

Dustinsfl

$$3776-1976+1-\left(\left \lfloor \frac{3776}{17} \right \rfloor - \left \lfloor \frac{1976}{17} \right \rfloor + 1\right)=1694$$

The answer is supposed to be 1695 though.

12. Jun 15, 2010

Staff: Mentor

That's what I get.

13. Jun 15, 2010

Dustinsfl

What do you get? 1694 or 1695?

14. Jun 16, 2010

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.

15. Jun 16, 2010

jeppetrost

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