Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I stumbled upon the following in a book:

till 400 all even numbers will be divisible by 2 ( 200 even numbers) remaining 200 odd numbers 1 3 5 7 9 ..... 399 200/3 = 67 will be divisible by 3, as we have discarded all even numbers and out of remaining numbers 2nd number is 3 then 1 + 198/3 = 67 numbers are divisible by 3

now we have discarded all multiples of 2 and 3 remaining numbers will be 200 - 67 = 133; 1 5 7 11 13 ... so on out of these 133 numbers 2nd number is 5 so numbers divisible by 5 will be 1 + 131/5 = 1+26 = 27

now remaining numbers = 133 - 27 = 106; 1 7 11 13 .. so on again 2nd number is 7 , so numbers divisible by 7 = 1 + 104/7 = 1+14 = 15

total numbers from 1 - 400 divisible by any of 2 3 5 7 = 200+67+27+15 = 309

But I can't seem to understand how the following is derived? :

as we have discarded all even numbers and out of remaining numbers 2nd number is 3 then 1 + 198/3 = 67 numbers are divisible by 3

How does the result come out to be "1 + 198/3" ?

share|improve this question
add comment

3 Answers

up vote 1 down vote accepted

The statement breaks down the calculation to show inclusiveness. Since 1 is not divisible by 3, There are 199 terms in the sequence, so there are 199/3 = 198/3 = 66 multiples of 3. Yet, inclusively, we need to count the last term in the sequence, 399, which is our +1.

Check #16 "http://math.ucsd.edu/~wgarner/math104a/hw/104ahw1.pdf"

share|improve this answer
    
The series starts with 1 : 1 3 5 7 and so there should be no need of applying inclusiveness, since inclusiveness is required when both ends are required but 1 is not a multiple of 3 –  Kartik Anand May 31 '12 at 14:03
    
Well 1 is obviously not divisible by 3, so our sequence becomes 199 integers: 3,5,7,9,...,399. Again, we have 66 multiples of 3: 199/3, plus the endpoints + 1. I believe "the 2nd number is three" in the original problem refers to this method. –  rckrd May 31 '12 at 14:11
    
Ater some work, I got it.Thanks –  Kartik Anand May 31 '12 at 14:17
add comment

The term in question, $1+198/3,$ comes from the observation that to count the odd numbers $$1, 3, \dots 399$$ that are divisible by 3, the author discards 1 (obviously not divisible by 3) and 3 (obviously divisible by 3), leaving 198 odd numbers. They are all of the form $2n+3$ for $n = 1, 2, \dots, 198$ exactly one-third of these, namely when $n=3, 6, \dots, 198$ are divisible by 3, so the total number of odd integers in the range will be 1 (for the 3 the author omitted) plus $198/3.$

It's worth mentioning that there's a more general way of solving such problems, namely the Inclusion-Exclusion principle. In its simplest form it states that if you have two finite sets, $S_1, S_2,$ then their sizes are related by $$\mid S_1 \cup S_2\mid = \mid S_1 \mid + \mid S_2 \mid-\mid S_1 \cap S_2 \mid$$ This is clear once one recognizes that the terms $\mid S_1\mid+\mid S_2\mid$ on the right count the elements in the intersection twice, so we correct the count by subtracting the elements in the intersection to get the total number of elements in either of $S_1$ or $S_2.$

This holds for more than two sets. In particular, for four sets we'll have \begin{align*} \mid S_1\cup S_2\cup S_3\cup S_4\mid &= \mid S_1 \mid+\mid S_2 \mid+\mid S_3 \mid + \mid S_4 \mid\\ &- \mid S_1\cap S_2\mid-\mid S_1\cap S_3\mid-\dots-\mid S_3\cap S_4\mid\\ &+ \mid S_1\cap S_2\cap S_3\mid+\dots+\mid S_2\cap S_3\cap S_4\mid\\ &-\mid S_1\cap S_2\cap S_3\cap S_4\mid \end{align*} In other words on the right you add the sizes of the sets, subtract the sizes of the two-set intersections, add the sizes of the three-element intersections, and so on.

Now in your problem, we have the general result that the number of integers in the range $1, \dots 400$ which are divisible by an integer $d$ will be $\lfloor 400/d\rfloor$, so if you let $S_1$ be the elements in the range divisible by 2, $S_2$ be the elements divisible by 3, $S_3$ the ones divisible by 5, and $S_4$ the ones divisible by 7 you'll have

\begin{align*} \mid S_1\cup S_2\cup S_3\cup S_4\mid &= 200+133+80+59\\ &- 66-40-28-26-19-11\\ &+ 13+9+5+3\\ &-1\\ &= 309 \end{align*} where, for example, $\mid S_1\cap S_2\mid$ is the number of elements in the range that are divisible by both 2 and 3 (namely by 6) so $\mid S_1\cap S_2\mid = 400/6 = 66$. Finally, the left-hand term, $\mid S_1\cup S_2\cup S_3\cup S_4\mid$ will count all the numbers in the range divisible by 2 or 3 or 5 or 7, which is what the author wanted.

share|improve this answer
add comment

If I understand things correctly, we have eliminated the even numbers. So we want to find how many of the remaining numbers are divisible by $3$. I do not know for sure how the expression $1+\frac{198}{3}$ was reached. But here is some reasoning that maybe is close to what is intended. Anyway, it is a useful kind of trick.

We are interested in counting the odd numbers up to $400$ which are multiples of $3$. These are the numbers $$3, 9, 15, 21, \dots, 393, 399.$$

There are just as many of these as there are numbers in the list $$0, 6, 12, 18, \dots, 390, 396$$ (we subtracted $3$ from every number in the first list). There are just as many of these as there are in the list $$0, 1, 2, 3, \dots, \frac{390}{6}$$ (we divided everybody by $6$). This final list consists of $0$ ($1$ number) plus all the integers from $1$ to $\frac{396}{6}$, inclusive. Note that $\frac{396}{6}=\frac{198}{3}$, and of course there are $\frac{198}{3}$ integers from $1$ to $\frac{198}{3}$, inclusive.

The actual reasoning could have been a slight variant. Get to the list $$0,6, 12, 18, \dots, 390, 396$$ as before. These are the even numbers up to $396$ that are divisible by $3$. There are just as many of these as there are numbers from $0$ to $198$ that are divisible by $3$. Write down a $1$ for the number $0$. Now we want the numbers from $3$ to $198$ that are divisible by $3$. there are $198/3$ of these.

Remark: What I would do is to say there are just as many in the list $3,9,\dots, 399$ as there are numbers in the list $6,12,\dots, 402$. (So I added $3$ to everybody.) And there are $402/6$ of these.

share|improve this answer
    
wow this is good, but I am not able to apply for the next step,i.e., after this 1 5 7 11 13 17 19 will be left, and the no. of numbers divisible by 5 will be 1 + 131/5, so I guess there is something else to the question –  Kartik Anand May 31 '12 at 13:51
    
But your way is not applicable when numbers divisible by 5 are required? –  Kartik Anand May 31 '12 at 14:06
    
It will work, basically same reasoning, but a bit more complicated. –  André Nicolas May 31 '12 at 14:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.