I have the general algorithm here that my teacher gave us( see full at http://i.imgur.com/pbzQb.png) picture )

To count we just divide, correct?

like - 1000/3 = 333 ?

What is the sigma notation used here(it's for principle of inclusion, exclusion I thiink)? Also, I am wondering about the boundary cases: near 1000.

Update: I am close I think i can do this :)


$\sum_{i=1}^4 N_i$ is shorthand for $N_1+N_2+N_3+N_4$.

Similarly, $\sum_{i,j=1}^4N_{ij}$ means write down all the numbers of the form $N_{ij}$ where $i$ and $j$ take on the values from 1 to 4, and add them up. However, that's not really what you want: you really want $\sum_{1\le i\lt j\le4}N_{ij}$, which is $N_{12}+N_{13}+N_{14}+N_{23}+N_{24}+N_{34}$.

EDIT: Actually, it appears from your $N_{3,4,5,6}$ that what you really want is for your sums to go from 3 to 6, not from 1 to 4, e.g., you want $\sum_{i=3}^6N_i=N_3+N_4+N_5+N_6$.


The number of multiples of $k$ that are less than or equal to some integer $n$ is $\left\lfloor\frac{n}k\right\rfloor$, the largest integer $\le\frac{n}k$. For instance, the number of multiples of $3$ less than or equal to $10$ is $\left\lfloor\frac{10}3\right\rfloor=3$: they are $3,6$, and $9$. Thus, in your problem $N_3=\left\lfloor\frac{1000}3\right\rfloor=333$, $N_4=\left\lfloor\frac{1000}4\right\rfloor=250$, and so on. There's no problem with numbers near $1000$.

The calculation that you're trying to do is indeed an inclusion-exclusion calculation, but your notation needs to be fixed. If $N_3,N_4,N_5$, and $N_6$ are respectively the numbers of multiples of $3,4,5$, and $6$ less than or equal to $1000$, then you don't want $$\sum_{i=1}^4N_i\;:$$ that means $N_1+N_2+N_3+N_4$, and you don't even have an $N_1$ or $N_2$. You want $$\sum_{i=3}^6N_i=N_3+N_4+N_5+N_6\;.$$ This is standard summation notation.

The idea of the inclusion-exclusion calculation is that a first approximation to $N$, the number of multiples of $3,4,5$, or $6$ less than or equal to $1000$, can be obtained by adding together the number of multiples of $3$, of $4$, of $5$, and of $6$: $$N\approx\sum_{i=3}^6N_i=N_3+N_4+N_5+N_6\;.\tag{1}$$ Of course this is a very bad approximation, since these categories overlap a lot, as in your Venn diagram. For instance, $15$ is both a multiple of $3$ and a multiple of $5$, so $(1)$ counts it twice. Therefore we count the numbers that are multiples of both $3$ and $5$ and subtract that number to correct for the double-counting in $(1)$. Specifically, if $N_{j,k}$ is the number of positive integers less than or equal to $1000$ that are divisible by both $j$ and $k$, we want to subtract $N_{j,k}$ from the total in $(1)$. There are actually six such pairs; their counts are $N_{3,4},N_{3,5},N_{3,6},N_{4,5},N_{4,6}$, and $N_{5,6}$. Using summation notation we can represent the sum of these numbers as $$\sum_{3\le j<k\le 6}N_{j,k}=N_{3,4}+N_{3,5}+N_{3,6}+N_{4,5}+N_{4,6}+N_{5,6}\;,$$ and we want to subtract this from $(1)$ to get a second, better approximation:

$$N\approx\sum_{k=3}^6N_k-\sum_{3\le j<k\le 6}N_{j,k}\;.\tag{2}$$

Unfortunately, it turns out that we've overcorrected: a number like $60$ that is a multiple of $3,4$, and $5$, say is counted $3$ times in $(1)$, and both counted and removed $(3)$ times in $(2)$, so it isn't counted at all in $(2)$.

To correct for this, we count the numbers that are multiples of three of the divisors $3,4,5$, and $6$ and add them back in. There are four such combinations, whose counts are $N_{3,4,5},N_{3,4,6},N_{3,5,6}$, and $N_{4,5,6}$. Their sum is

$$\sum_{3\le i<j<k\le 6}N_{i,j,k}=N_{3,4,5}+N_{3,4,6}+N_{3,5,6}+N_{4,5,6}\;,$$

and we get our third approximation by adding it back in:

$$N\approx\sum_{k=3}^6N_k-\sum_{3\le j<k\le 6}N_{j,k}+\sum_{3\le i<j<k\le 6}N_{i,j,k}\;.\tag{3}$$

Once again it turns out that we've overcorrected, so we subtract $N_{3,4,5,6}$, the number that are multiples of $3,4,5$, and $6$. At this stage we have an exact count:

$$N=\sum_{k=3}^6N_k-\sum_{3\le j<k\le 6}N_{j,k}+\sum_{3\le i<j<k\le 6}N_{i,j,k}-N_{3,4,5,6}\;.\tag{4}$$

Of course if we'd really been thinking, we could have ignored the multiples of $6$ from the start: every multiple of $6$ is already a multiple of $3$, so there's no point counting it separately. Thus, the inclusion-exclusion formula could have been reduced to $$N=\Big(N_3+N_4+N_5\Big)-\Big(N_{3,4}+N_{3,5}+N_{4,5}\Big)-N_{3,4,5}\;.$$

  • 1
    $\begingroup$ That every multiple of 6 is a multiple of 2 seems to be irrelevant; that every multiple of 6 is a multiple of 3 is the reason we can ignore multiples of 6, right? $\endgroup$ – Gerry Myerson May 10 '12 at 1:56
  • $\begingroup$ @Gerry: Yep. For some reason I was thinking that $2$ was in the divisor set when I wrote that. Thanks; fixed. $\endgroup$ – Brian M. Scott May 10 '12 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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