# How do I accurately count the integers(1-1000) that are not divisible by 3,4,5,6?

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

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}\;.$$

-
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? – Gerry Myerson May 10 '12 at 1:56
@Gerry: Yep. For some reason I was thinking that $2$ was in the divisor set when I wrote that. Thanks; fixed. – Brian M. Scott May 10 '12 at 1:58