Inclusion-Exclusion Convergence

Question

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.

Answer 1

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. $$