Welcome guest
You're not logged in.
309 users online, thereof 1 logged in

## Definition: Sieve, Sieve Problem

A sieve is a tuple $(\mathcal A_N,\mathcal P_\rho,\mathcal R)$ consisting of

• $\mathcal A_N:=\{a_1,\ldots,a_N\}\subset\mathbb N$, i.e. a subset of $N$ (not necessarily consecutive) natural numbers,
• $\mathcal P_\rho:=\{p_1,\ldots,p_\rho\}\subset\mathbb P$, i.e. a subset of $\rho$ (not necessarily consecutive) prime numbers.
• $\mathcal R$ is a union of congruence classes
$$\mathcal R:=\bigcup_{r=1}^\rho\bigcup_{j=1}^{k_r}R_{r}^{(j)},$$
where for $r=1,\ldots,\rho$, some $k_r$ congruence classes $R_r^{(1)},\ldots,R_r^{(k_r)}$ are given modulo each prime number $p_r$.

Given a sieve, a sieve problem is the problem of estimating the cardinality of all elements of $\mathcal A$ that are not congruent to any of the residue classes in $\mathcal R$, i.e. the number $$S(N):=|\{n\in\mathbb N\mid a_n\not\in R\}|.$$

| | | | | created: 2020-05-17 11:58:07 | modified: 2020-05-17 12:18:33 | by: bookofproofs | references: [8526], [8527]