This HWA section gets its own debrief document because we needed to do other things in class. This document is a Jupyter notebook that you can either simply read and enjoy, or you can upload it to SageMath Cloud and play with it interactively.
%
operator¶In Python and in Sage, the %
operator is used to return the remainder that occurs when dividing one integer by another. For example, dividing 23 by 5 leaves a remainder of 3, so 23 % 5 = 3
.
The %
(pronounced 'mod') operator is handy for testing whether one integer is divisible by another. Can you think of how? Or, can you see how in the code snippets below?
How many integers between 1000 and 9999 (including 1000 and 9999) are there that are divisible by 9?
First of all let's find the smallest integer in this range that's divisible by 9. We can do this with the %
operator and a little guess-and-check.
1008 % 9
0
Looks like it's 1008. The next one is 1017, which is 9 units away from 1008. Then the next one is 1026, another 9 units away. In fact all of these divisible-by-9 numbers are 9 units apart, so all we need to do is think about how many jumps of 9 units are there between 1000 and 9999.
This is the same question as: If we take the numbers between 1000 and 9999 and group them into groups of 9 each, how many groups are there? Now it's easy: We just need to take the number of integers from 1000 and 9999, and divide that number by 9. (Analogy: There are 32 students in one of my classes. How many groups are there if I form groups of 4?)
There are 9000 integers between 1000 and 9999, so the number of integers in this range divisible by 9 is $9000/9 = 1000$.
The code snippet below finds them all (in the list divisible_by_nine
) and then finds how many (len
).
divisible_by_nine = [x for x in range(1000, 10000) if x % 9 == 0]
len(divisible_by_nine)
1000
How many even numbers are there in this range?
This one is a lot easier because exactly half of the integers are even. Since our range from 1000-9999 is an even length, we just find the number of integers in this range and divide by 2. That would be $9000/2 = 4500$.
How many integers in this range have distinct digits?
This means, all the digits are different. We can count these using the law of products.
So, that's $9 \times 9 \times 8 \times 7 = 4536$ of those. (Which, oddly enough, is one of the integers we just counted because it has distinct digits.)
How many integers in this range are not divisible by 3?
Here we will employ a useful strategy for combinatorics problems which is to approach the problem from the backwards direction. Let's count the number of integers that are divisible by 3; then the number of integers that aren't divisible by 3 will be 9000 minus this number because there are 9000 integers in the range all totalled, and the set of integers that are divisible by 3 and the set of the ones that aren't, are disjoint.
We saw how to count this kind of thing in the first problem -- just divide 9000 by (this time) 3. That gives 3000. Therefore the number of integers not divisible by 3 is $9000 - 3000 = 6000$. Here's some code to check:
not_divisible_by_three = [x for x in range(1000, 10000) if x % 3 != 0]
len(not_divisible_by_three)
6000
How many integers in this range are divisible by either 5 or 7?
This will be equal to the number that are divisible by 5, plus the number that are divisible by 7, minus the number that are divisible by both 5 and 7. That's the rule of sums.
Mimicking the solution for problems 1 and 4, the number of integers in this range divisible by 5 is $9000/5 = 1800$.
Finding the number divisible by 7 is trickier because 9000 is not itself divisible by 7. If we just divide we get a decimal. So, we need to round -- but which way?
Let's play around with a smaller case to see what we should do.
If we just looked at the integers between 1000 and 1050 (sort of a smaller version of the range we use in the main problem), we get 1001, 1008, 1015, 1022, 1029, 1036, 1043, 1050. That's 8 of those; and notice that $51/7 \approx 7.2$. We divide into 51 because there are 51 integers from 1000 ro 1050. That makes us think we ought to round up.
Let's try one more case, from 1000 to 1099: 1001, 1008, 1015, 1022, 1029, 1036, 1043, 1050, 1057, 1064, 1071, 1078, 1085, 1092, 1099. That's 15 in all. Note: $100/7 \approx 14.29$ so we round up again.
If we stop here and generalize, we should compute
$$\lceil 9000/7 \rceil = 1286$$Let's cheat and use some code to see what that number is:
div_by_seven = [x for x in range(1000,9999) if x % 7 == 0]
len(div_by_seven)
1286
Boom.
So there are 1800 integers in range divisible by 5 and 1286 of them divisible by 7. How many are divisible by both 5 and 7? Well, if you are divisible by both 5 and 7 then you must be divisible by 35 (which is $5 \times 7$). (Note: This is true because 5 and 7 are both prime numbers. This argument doesn't work if the two numbers share a common divisor.)
That count is
div_by_35 = [x for x in range(1000,9999) if x % 35 == 0]
len(div_by_35)
257
We are finally ready to answer the question. Let $A$ be the set of integers in this range that are divisible by 5. Let $B$ be the set of integers in this range that are divisible by 7. Then the number of integers in this range that are divisible by either 5 or 7 is:
$$|A \cup B| = |A| + |B| - |A \cap B| = 1800 + 1286 - 257 = 2829$$How many integers in this range are divisible by both 5 and 7?
This is out of order, but we just answered it: 257 of them.
How many integers in this range are not divisible by either 5 or 7?
Well, we just counted the number of integers in the range that are divisible by either 5 or 7, and that count was 2829. So the number of integers that aren't would be all the others, of which there are $9000-2829 = 6171.$
How many integers in this range are divisible by 5 but not by 7?
Since in order to be divisible by 5 and by 7, the integer has to be divisible by 35, this question is the same thing as asking
How many integers in this range are divisible by 5 but not by 35?
This may not seem any easier to answer, until you start listing out some multiples of 5 and see a pattern. To see this, start all the way back at 0:
$$5, 10, 15, 20, 25, 30, \mathbf{35}, 40, 45, 50, 55, 60, 65, \mathbf{70}, 75, \dots$$The ones in bold are the ones divisible by 35 and notice they come at regular intervals: every seventh one. Which makes sense when you think about 35 equalling $5 \times 7$. So if we wanted to find, say, all the integers that are divisible by 5 but not by 35 between 1 and 100, we'd need to find all the numbers divisible by 5 and remove 1/7 of them. In this case (from 1 to 100) that would be 20 integers in all and remove $\lfloor 20/7 \rfloor = 2$ of them for a total of 18, which you can check by brute force.
Now just generalize this: Starting at 1000 (which is not divisible by 35) and going to 9999, we already found there were 1800 integers divisible by 5. We will remove $\lfloor 1800/7 \rfloor = 257$ of those, and we're left with $1800 - 257 = 1543$.
Checking with code:
five_not_seven = [x for x in range(1000,10000) if x % 5 == 0 and x % 7 != 0]
len(five_not_seven)
1543
What I hope you learn from this exercise is: