# Inclusion-Exclusion Convergence

I made a sequence of terms using the inclusion exclusion principle and odd primes and was wondering whether it converged to $\frac{n}{2}$, which was my original hope. It looks like this: $$\lfloor\frac{n}{6}\rfloor+\lfloor\frac{n}{10}\rfloor+...+\lfloor\frac{n}{2p}\rfloor- (\lfloor\frac{n}{30}\rfloor+... \lfloor\frac{n}{2p_i p_{i+1}}\rfloor+...) +\lfloor\frac{n}{210}\rfloor+\lfloor\frac{n}{2p_i p_{i+1} p_{i+2}}\rfloor+...-...+...-\frac{n}{2*\prod_{k=2}^{\pi(n)}p_k}$$ I hope the pattern is clear here. In your answer, please discuss why or why not the expression converges to $\frac{n}{2}$, and what it represents.

Let $\mathbf{P}'$ denote the set of odd primes. Then I guess what you want to form is the following quantity

$$\begin{split} S_n &= \sum_{p \in \mathbf{P}'} \#[\text{multiples of 2p in \{1, \cdots, n\}}] \\ &\hspace{2em} - \sum_{\substack{p, q \in \mathbf{P}' \\ p < q}} \#[\text{multiples of 2pq in \{1, \cdots, n\}}] \\ &\hspace{4em} + \sum_{\substack{p, q, r \in \mathbf{P}' \\ p < q < r}} \#[\text{multiples of 2pqr in \{1, \cdots, n\}}] \\ &\hspace{6em} - \cdots \end{split} \tag{1}$$

From the inclusion-exclusion principle, this corresponds to

$$S_n = \#[k \in \{1,\cdots,n\} : \text{k is even and not a power of 2}].$$

When $n \geq 2$, this expression leads to

$$S_n = \left\lfloor \frac{n}{2}\right\rfloor - \left\lfloor\log_2 \frac{n}{2} \right\rfloor.$$

Let $[n] = \{1,\cdots,n\}$. Notice that the sum $S_n$ can be written as

$$S_n = \sum_{p\in\mathbb{P}'} |[n]\cap 2p\Bbb{Z}| - \sum_{p<q\in\mathbb{P}'} |[n]\cap 2p\Bbb{Z}\cap 2q\Bbb{Z}| + \sum_{p<q<r\in\mathbb{P}'} |[n]\cap 2p\Bbb{Z}\cap 2q\Bbb{Z}\cap 2r\Bbb{Z}| - \cdots$$

so that it is obtained by applying the inlusion-exclusion principle to the union

$$\Bigg| \bigcup_{p\in\mathbf{P}'} ([n]\cap 2p\Bbb{Z}) \Bigg|.$$

If we instead apply the inclusion-exclusion principle to

$$\Bigg| \bigcup_{p\text{ prime}} ([n]\cap p\Bbb{Z}) \Bigg|,$$

since $1$ the unique element in $[n]$ which is not a multiple of prime, the result will be

$$n-1 = \sum_{p\text{ prime}} |[n]\cap p\Bbb{Z}| - \sum_{p<q\text{ prime}} |[n]\cap p\Bbb{Z}\cap q\Bbb{Z}| + \sum_{p<q<r\text{ prime}} |[n]\cap p\Bbb{Z}\cap q\Bbb{Z}\cap r\Bbb{Z}| - \cdots.$$

• How did you get the $\left\lfloor\log_2 \frac{n}{2} \right\rfloor$ term? May 24, 2017 at 13:12
• @LinusRastegar That term counts the number of powers of 2 contained in $\{2, 3, \cdots, n\}$. May 24, 2017 at 13:15
• Thanks for the speedy reply. I will hold off on checking this as the answer until I have some other input as well. May 24, 2017 at 13:50
• I've done some thinking about your answer--does my sequence also represent the number of multiples of $p$ but not $2p$? May 24, 2017 at 19:21
• If my sequence does not represent the number of multiples of $p$ but not $2p$ how might I fix it? I would greatly appreciate it if you could answer this since this is also part of the question. May 28, 2017 at 2:44