Problem Statement
Let $n_1<n_2<\cdots $ be an infinite sequence of integers with associated $a_k\pmod{n_k}$, such that for some $\epsilon>0$ we have $n_k>(1+\epsilon)k\log k$ for all $k$. Then\[\#\{ m<n_k : m\not\equiv a_i\pmod{n_i} \textrm{ for }1\leq i\leq k\}\neq o(k).\]
Categories:
Number Theory Covering Systems
Progress
Erdős and Graham [ErGr80] suggest this 'may have to await improvements in current sieve methods' (of which there have been several since 1980).Note that since the $k$th prime is $\sim k\log k$ the lower bound $n_k>(1+\epsilon)k\log k$ is best possible here.
Cambie has observed that this question has a trivial negative answer, since taking $n_k=2^k$ and $a_k=2^{k-1}+1$ for $k\geq 1$ implies the only $m$ not in any congruence class is $1$, so the count is actually $1$!
For further discussion on counterexamples, and what a non-trivial variant of this problem might be, see the comments.
Source: erdosproblems.com/280 | Last verified: January 14, 2026