inclusion/exclusion

**noles2188** · November 18th 2008, 08:14 PM

Use the principle of inclusion/exclusion to determine how many numbers between 1 and 1000 are
a) not divisible by 2, 3, 5, or 7

b) not perfect n-th powers for any n>1 (not perfect squares, not perfect cubes, etc)

c) not square free (not divisible by n^2 for any n>1)

**Soroban** · November 18th 2008, 09:27 PM

Hello, noles2188!

Here's the first one . . .

Use the principle of inclusion/exclusion to determine how many numbers
between 1 and 1000 are: .a) not divisible by 2, 3, 5, or 7

We will find how many numbers are divisible by 2, 3, 5, or 7.

. . $\begin{array}{c|c} \text{Div.by} & \text{Quantity} \\ \hline \\[-4mm] 2 & \left[\tfrac{1000}{2}\right] \:=\:500 \\ \\[-3mm] 3 & \left[\tfrac{1000}{3}\right] \:=\:333 \\ \\[-3mm] 5 & \left[\frac{1000}{5}\right] \:=\:200 \\ \\[-3mm] 7 & \left[\frac{1000}{7}\right] \:=\:142 \end{array} \qquad \text{Total: }1175$

. . $\begin{array}{c|c} \text{Div.by} & \text{Quantity} \\ \hline \\[-3mm] 2,3 & \left[\frac{1000}{6}\right] \:=\:166 \\ \\[-3mm] 2,5 & \left[\frac{1000}{10}\right] \:=\:100 \\ \\[-3mm] 2,7 & \left[\frac{1000}{14}\right] \:=\:71 \\ \\[-3mm] 3,5 & \left[\frac{1000}{15}\right] \:=\:66 \\ \\ [-3mm] 3,7 & \left[\frac{1000}{21}\right] \:=\:47 \\ \\[-3mm] 5,7 & \left[\frac{1000}{35}\right] \:=\:28 \end{array}\qquad\text{Total: }414$

. . $\begin{array}{c|c} \text{Div.by} & \text{Quantity} \\ \hline \\[-3mm] 2,3,5 & \left[\frac{1000}{30}\right] \:=\:33 \\ \\[-3mm] 2,3,7 & \left[\frac{1000}{42}\right] \:=\:23 \\ \\[-3mm] 2,5,7 & \left[\frac{1000}{70}\right] \:=\:14 \\ \\[-3mm] 3,5,7 & \left[\frac{1000}{105}\right] \:=\:9 \end{array}\qquad\text{Total: } 79$

. . $\begin{array}{c|c} \text{Div.by} & \text{Quantity} \\ \hline \\[-3mm] 2,3,5,7 & \left[\frac{1000}{210}\right] \:=\:4 \end{array} \qquad \text{total: }4$

Divisible by 2, 3, 5, or 7: . $1175 - 414 + 79 - 4 \;=\;836$

Therefore, not divisible by 2, 3, 5, or 7: . $1000 - 836 \;=\;\boxed{164}$

Anyone care to check my work . . . please?
.

**noles2188** · November 18th 2008, 10:31 PM

I found a mistake in the total of divisible by 2,3 or 2,5 etc. The total is 478 not 414. Other then that, it all works out...thanks a lot.

Thread: inclusion/exclusion

LinkBack

Thread Tools

Display

inclusion/exclusion

Similar Math Help Forum Discussions

Inclusion Exclusion

Inclusion/Exclusion

inclusion & exclusion help

Inclusion/Exclusion

Inclusion-exclusion

Search Tags