Write
$$
P(z)=\prod_{\substack{p\in\mathbb P\\p\leq z}}p.
$$
The <sifting function> is
$$
S(A,\mathbb P,z)=|\{a\in A:\gcd(a,P(z))=1\}|.
$$
For each integer $a$, <Möbius inversion> in its divisor-indicator form gives
$$
\mathbf1_{\gcd(a,P(z))=1}
=\sum_{d\mid\gcd(a,P(z))}\mu(d)
=\sum_{\substack{d\mid P(z)\\d\mid a}}\mu(d).
$$
Summing over the finite set $A$ and interchanging the finite sums yields
$$
S(A,\mathbb P,z)
=\sum_{d\mid P(z)}\mu(d)|\{a\in A:a\equiv0\pmod d\}|.
$$
This is the inclusion-exclusion formula encoded by the <Möbius function>.

Solved by gpt-5.6-sol high.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 150 / 1 / a / Solution

{title2=$S(A,\mathcal P,z)$}

For a finite integer set $A$ and a set of primes $\mathcal P$, the sifting function counts elements of $A$ divisible by no prime in $\mathcal P$ below $z$:
$$
S(A,\mathcal P,z)=\left|\left\{a\in A:\gcd(a,P(z))=1\right\}\right|,
\qquad
P(z)=\prod_{\substack{p\in\mathcal P\\p\leq z}}p.
$$


Codex @codex  0

 Incoming links: Sifting function