If there is a set {1,2,3,...,1000} How many numbers are left if all multiples of 2 3 5 7 are crossed out.

Results 1 to 5 of 5

- Jan 14th 2008, 12:07 AM #1

- Joined
- Jan 2008
- Posts
- 2

- Jan 14th 2008, 02:17 AM #2

- Jan 14th 2008, 02:37 AM #3

- Joined
- Jan 2008
- Posts
- 2

- Jan 14th 2008, 03:56 PM #4

- Jan 14th 2008, 06:38 PM #5

- Joined
- Nov 2005
- From
- New York City
- Posts
- 10,616
- Thanks
- 10

Notation: $\displaystyle a|b$ reads "$\displaystyle a$ divides $\displaystyle b$"

Let $\displaystyle S = \{1,2,...,1000\}$

Let $\displaystyle A = \{ x \in S : 2|x \}$

Let $\displaystyle B = \{ x \in S : 3| x\}$

Let $\displaystyle C = \{x \in S : 5|x\}$

Let $\displaystyle D = \{ x \in S : 7|x\}$.

Now,

$\displaystyle |A\cup B \cup C \cup D| = |A|+|B|+|C|+|D| - |A\cap B| - |A\cap C| - |A\cap D| - |B\cap C| - |B\cap D| - |C\cap D|$$\displaystyle +|A\cap B\cap C|+|A\cap B\cap D|+|A\cap C \cap D|+|B\cap C\cap D| - |A\cap B\cap C\cap D|$

Now,

$\displaystyle |A| = 500$

$\displaystyle |B|= 333$

$\displaystyle |C| = 200$

$\displaystyle |D|=142$

When you reach the mixed ones it is easy. Because $\displaystyle \gcd$ between any two of $\displaystyle 2,3,5,7$ is $\displaystyle =1$ it means that, for example, $\displaystyle A\cap B = \{ x\in S : 6 | x\}$ and $\displaystyle A\cap B\cap C = \{ x\in S : 30|x\}$. And so on.