3

An integer is called squarefree if it is not divisible by the square of a positive integer greater than $1$. Find the number of squarefree positive integers less than $100$.

My attempt: I apply the inclusion-exclusion principle directly.

  • Total number of integers = 99
  • Number of integers divisible by $2^2$ = $24$
  • Number of integers divisible by $3^2$ = $11$
  • Number of integers divisible by $4^2$ = $6$
  • Number of integers divisible by $5^2$ = $3$
  • Number of integers divisible by $6^2$ = $2$
  • Number of integers divisible by $7^2$ = $2$
  • Number of integers divisible by $8^2$ = $1$
  • Number of integers divisible by $9^2$ = $1$
  • Number of integers divisible by $2^2$ and $3^2$ = $2$
  • Number of integers divisible by $2^2$ and $4^2$ = $1$

Then the required solution would be $99-(24+11+6+3+2+2+1+1)+2+1=52$. But the solution is $61$. Where is my mistake?

Nighty
  • 2,152
  • 1
    For example : If $4^2$ divides n, then $2^2$ also divides $n$. So, you cannot just add all the numbers. – Peter Nov 01 '15 at 12:29
  • 2
    you are double counting (or double subtracting). $36$, for example, is divisible by both $2^2$ and $3^2$ so you subtract it twice. – lulu Nov 01 '15 at 12:29
  • The correct approach : Number of multiples of $4$ : $24$ , number of multiples of $9$ : $11$ number of multiples of $25$ : 3 , number of multiples of $49$ : $2$ , number of multiples of $36$ : 2 : Now $99-(24+11+3+2-2)=61$ – Peter Nov 01 '15 at 12:37

4 Answers4

6

An integer is square-free if and only if none of its prime factors appear with an exponent $\ge 2$ in its prime factorization.

The only primes that can appear with an exponent of 2 or more in a number less than $100$ are those that are less than $\sqrt{100}=10$, that is, $2$, $3$, $5$, and $7$.

So the numbers you need to exclude are just those that are multiples of $4$, $9$, $25$ or $49$.

Neither of the multiples of $25$ and $49$ are multiples of any of the other squares, so they can be subtracted separately. All we need to care about is the double-counting of multiples of $36$, so:

  • Start with $99$ possible numbers.
  • Subtract $24$ multiples of $4$.
  • Subtract $11$ multiples of $9$.
  • Add back $2$ because $36$ and $72$ were each subtracted twice.
  • Subtract $3$ multiples of $25$.
  • Subtract $2$ multiples of $49$.

$$ 99 - 24 - 11 + 2 - 3 - 2 = 61 $$

hmakholm left over Monica
  • 286,031
3

If $4^2$ divides $n$ then so does $2^2$, so your method double-counts. A number is nonsquarefree iff it is divisible by a square of a prime, so we can proceed as follows:

Let $A_k$ denote the numbers (here, positive integers) less than $100$ divisible by $k^2$. Since $$ |A_k| = \left\lfloor \frac{100 - 1}{k^2} \right\rfloor ,$$ we have $|A_k| = 0$ for $k \geq 10$. Then, applying the inclusion-exclusion principle to the sets $A_p$, $p < 10$ prime, gives that the number of nonsquarefree numbers less than $100$ is

\begin{multline}|A_2| + |A_3| + |A_5| + |A_7| \\- (|A_2 \cap A_3| + |A_2 \cap A_5| + |A_2 \cap A_7| + |A_3 \cap A_5| + |A_3 \cap A_7| + |A_5 \cap A_7|) + \cdots ,\end{multline} where $\cdots$ denotes terms containing cardinalities of intersections of three and four sets.

Now, $n \in A_q \cap A_{q'}$ for $q, q'$ coprime iff $n$ is divisible by both $q^2$ and $(q')^2$, and hence by coprimality, by $q^2 (q')^2 = (qq')^2$, so $A_q \cap A_{q'} = A_{qq'}$. So, for example, $A_2 \cap A_5 = A_{10}$, which by the above is empty, and the same is true for all of the intersections of two sets except $A_2 \cap A_3 = A_6$. Similarly, by induction, the triple and quadruple intersections are all empty. This leaves that the number of nonsquarefree numbers less than $100$ is $$|A_2| + |A_3| + |A_5| + |A_7| - |A_6| .$$

Travis Willse
  • 99,363
2

Something that may come in handy if you don't need the exact number of squarefree positive integers equal to or below $n$ and an approximation is sufficient: if we denote by $S(n)$ this quantity, we have:

$$ S(n) \approx \frac{n}{\zeta(2)}, $$

where $\zeta$ denotes the Riemann zeta function and

$$ \zeta(n) = \frac{\pi^2}{6} \approx 1.64493406684822\ldots $$

So in your case the number of positive integers that are squarefree below $100$ is

$$ \frac{100}{\zeta(2)} \approx 60.7927101\ldots, $$

which is not far from the actual value of $61$.

Klangen
  • 5,075
0

There are 6 integers divisible by 2^2 and 4^2, not 1. You are also not counting when integers are divisible by both 3^2 and 9^2, or 2^2, 4^2, and 8^2 for example. The other methods provided are easier to calculate, but your approach is correct except for these errors.

user1023545
  • 1