\problemdata      
        {?} % latex-friendly label for the prob.
        {Counting} % The topic(s) of the problem content.
        {?} % Source (if known)
        {Fall 2001, PS8; S01, TU8; S98, PS7} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).


\begin{problem}
{\bf Square-Free}
A positive integer is called {\em square-free} if it is not
divisible by the square of any positive integer greater than 1.  For
example $35 = 5 \cdot 7$ is square-free but $18 = 2 \cdot 3^2$ is
not.  $1$ is square-free.  Use inclusion-exclusion to find the
number of square-free positive integers strictly less than 151.

\solution{We use Inclusion-Exclusion as was done for
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l8.pdf}{rule}{count-primes}{counting
prime numbers} in Notes and Rosen.  So we compute the number of positive
integers less than 150 that are \emph{not} square-free.

Let $A_2$ (respectively, $A_3$, $A_5$, $A_7$, $A_{11}$) be the set of
multiples of $2^2$ (respectively, $3^2$, $5^2$, $7^2$, $11^2$) less than
150.  The union of these sets is the set of all numbers less than 150
which are not square-free, \ie have some square divisor in them.
The reader should take a moment to think through why this assertion
is true (why only primes? why stop at 11?).

The cardinality of this set can be computed by the Inclusion-Exclusion
Principle.  Since $2^2 7^2 > 150$ and $3^25^2 > 150$, it follows that $A_i
\intersect A_j = \emptyset$ unless $\set{i,j}=\set{2,3}$ or $\set{2,5}$,
so

\begin {eqnarray*}
\card{A_2 \cup A_3 \cup A_5 \cup A_7} & = &
|A_2| + |A_3| + |A_5| + |A_7| + |A_{11}|
- |A_2 \cap A_3 | - |A_2 \cap A_5|\\
& = & \lfloor 150/2^2 \rfloor +  \lfloor 150/3^2 \rfloor + \lfloor 150/5^2 \rfloor
+ \lfloor 150/7^2 \rfloor + \lfloor 150/11^2 \rfloor\\
& &  - \lfloor 150/2^23^2 \rfloor
- \lfloor 150/2^25^2 \rfloor\\
& = & 37 + 16 + 6 + 3 + 1 - 4 - 1\\
& = & 58
\end {eqnarray*}
Therefore, the number of square-free positive integers less than
150 is
\[
150 - 58 = 92.
\]
}
\end{problem}
