5
$\begingroup$

Question:

Let $Q(x)$ denote the number of square-free (quadratfrei) integers between $1$ and $x$

find $Q(2013)=?$

My try:I know $ 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39,\cdots $ Square-free integer,and How many numbers square-free integer from 1 to $2013$? see http://en.wikipedia.org/wiki/Square-free_integer

I know that Let $Q(x)$ denote the number of square-free (quadratfrei) integers between $1$ and $x$

then $$Q(x)\approx \dfrac{6x}{\pi^2}$$ then $$Q(2013)\approx \dfrac{6\times 2013}{\pi^2}\approx 1223.75\cdots$$

But Now $Q(2013)=?$

$\endgroup$
  • 1
    $\begingroup$ Somwhat unpleasant, but we can use Inclusion/Exclusion to count the numbers that are not square-free. We need only worry about primes squared. $\endgroup$ – André Nicolas Oct 21 '13 at 4:00
  • $\begingroup$ Hello,your mean $n-Q(n)$ is easy to find? Thank you $\endgroup$ – math110 Oct 21 '13 at 4:01
  • $\begingroup$ Yes, easy in principle: the ones divisible by $4$ are $\lfloor 2013/4\rfloor$ and so on. Last one we need to worry about is $\lfloor 2013/43^2\rfloor$. Only combinations of small primes will be subject to the Exclusion part. $\endgroup$ – André Nicolas Oct 21 '13 at 4:04
8
$\begingroup$

I don't think there's any way to compute $Q(N)$ exactly without doing something on the order of $\sqrt N$ calculations. However, here's a formula that organizes things:

$$Q(N)=\sum_{n=1}^\infty \mu(n)\left\lfloor{N\over n^2}\right\rfloor$$

where $\mu(n)$ is the Mobius function. The sum is actually always finite: You never have to go past $n=\sqrt N$. Basically, the Mobius function does the inclusion-exclusion that André Nicolas and Kieren MacMillan referred to.

For $N=2013$, we get

$$Q(2013)=2013-503-223-80+55-41+20-16-11+10+8-6-5\\ +4+4-3+2-2-2-2+1+1+1-1+1+1-1-1-1=1223$$

$\endgroup$
6
$\begingroup$

Here's how to work it out explicitly, with a modified Sieve of Eratosthenes approach (see also André Nicholas's comments regarding Inclusion/Exclusion).

There are $\lfloor{2013/4}\rfloor = 503$ numbers in that range divisible by $4=2^2$.

There are $\lfloor{2013/9}\rfloor = 223$ numbers divisible by $9 = 3^2$. However, $\lfloor{2013/36}\rfloor = 55$ of those will also be divisible by $4$, and will thus have been counted in the first pass. So this pass catches $168$.

There are $\lfloor{2013/25}\rfloor = 80$ numbers divisible by $25 = 5^2$. However, $\lfloor{2013/100}\rfloor = 20$ of those will be divisible by $100 = 2^2 \cdot 5^2$, and will thus have been counted in the first pass, and $\lfloor{2013/225}\rfloor = 8$ are divisible by $225=3^2 \cdot 5^2$. But now $2$ are counted twice in the reductions, so this pass actually catches $54$.

There are $\lfloor{2013/49}\rfloor = 41$ numbers divisible by $49 = 7^2$. However, $\lfloor{2013/196}\rfloor = 10$ of those will have been counted in the first pass, and $\lfloor{2013/441}\rfloor = 4$ will have been counted in the second pass, and $\lfloor{2013/1225}\rfloor = 1$. (This is what André Nicholas meant by "Only combinations of small primes will be subject to the Exclusion part".) Again, you need to find those that are excluded twice and add them back in. This pass gives $27$.

Continue this way until $\lfloor{2013/p^2}\rfloor < 1$ for some prime $p$ [n.b. as pointed out by André Nicholas, the last prime you need to check is $p=43$], and you will compute your answer by subtracting the number found in each pass from the original total, $2013$.

Hence your final answer is $$2013-503-168-54-27-\dots=1223.$$

$\endgroup$
  • 1
    $\begingroup$ I don't think you've done the inclusion-exclusion correctly. For example, the $41$ multiples of $7^2$ are $49,98,147,196,\ldots$. But $196$ was counted already, as a multiple of $2^2$. $\endgroup$ – Barry Cipra Sep 15 '14 at 18:15
  • $\begingroup$ Thanks! I think I corrected it. $\endgroup$ – Kieren MacMillan Sep 15 '14 at 18:33
  • 1
    $\begingroup$ OMG! The estimate $Q(x) = \dfrac{6x}{\pi^2}$ is already accurate! $\endgroup$ – Isomorphism Sep 15 '14 at 18:40
0
$\begingroup$

I think it's worth illustrating the role of $\mu(n)$, The Möbius function, in inclusion-exclusion as Barry Cipra alludes to.

We will calculate $Q(N)$. For the $i$th prime $p_i$ (considering only $p_i^2 \le N$) let $$A_i = \{p_i^2, 2p_i^2, \dots, p_i^2 \lfloor N / p_i^2 \rfloor \}$$

For example $A_1 = \{4, 8, 12, 16, \dots, 4 \lfloor N/4 \rfloor \}$, the multiples of $4$ that are less than or equal to $N$.

Let $i_{max}$ be the maximum $i$ such that $p_i^2 \le N$. We are looking for $$N - \left\vert \bigcup_{i=1}^{i_{max}} A_i \right\vert = N - \left( \sum_{1 \le i \le i_{max}} |A_i| \right) + \left( \sum_{1 \le i < j \le i_{max}} |A_i \cap A_j| \right) - \left( \sum_{1 \le i < j < k \le i_{max}} |A_i \cap A_j \cap A_k| \right) + \cdots $$

We see that $A_1 \cap A_2$ are numbers that are divisible by $4$ and $9$, or divisible by $36$. Similarly $A_1 \cap A_3$ are numbers divisible by $4 \cdot 25$ and $A_2 \cap A_3$ are numbers divisble by $4 \cdot 36$. $A_1 \cap A_2 \cap A_3$ are numbers divisible by $4 \cdot 25 \cdot 36$.

Directly from the inclusion-exclusion formula, we see we subtract out numbers that are the product of an odd number of squared (distinct) primes, and add in numbers that are the product of an even number of squared (distinct) primes. Let's say $n^2$ is this product of these squared primes. Then $n$ is the product of distinct primes. There are $\lfloor N/n^2 \rfloor$ of these values (see Kieren MacMillan's answer).

$\mu(n)$ is $-1$ when $n$ is the product of an odd number of distinct primes, $1$ when $n$ is the product of an even number of distinct primes, and $0$ if $n$ is not the product of distinct primes ($n$ is not square-free). This corresponds exactly to the adding and subtracting in our inclusion-exclusion formula! (Note that $\mu(n)=0$ means $n$ is not the product of distinct primes, and so is not considered in the inclusion-exclusion formula).

So we conclude that $\mu(n)$ is a handy way of encoding our inclusion-exclusion principle. $$Q(N) = \sum_{n=1}^{\lfloor \sqrt N \rfloor} \mu(n) \left\lfloor \frac{N}{n^2} \right\rfloor$$

To actually calculate $Q(N)$ we need $\mu(n)$ values up to $\sqrt N$. A variation of the Sieve of Eratosthenes calculates a range of $\mu(n)$ much more efficiently than calculating one value at a time. Algorithms listed on MO.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.