Choose $a_p\pmod p$ for every prime so all large $n$ are $a_p+tp$ with $t\geq k$ (Erdős #279)
Statement
Let $k\geq 3$. Is there a choice of congruence classes $a_p\pmod{p}$, one for every prime $p$, such that all sufficiently large integers can be written as $a_p+tp$ for some prime $p$ and integer $t\geq k$?
Acceptance. FULLY RESOLVES: a proof that for every $k\geq 3$ (or with $k$ arbitrary but explicit) such a choice of congruence classes exists, or a proof that for some stated $k\geq 3$ no choice works — machine-checkable (Lean/Coq) preferred, with the existing formal-conjectures statement as the target, else a complete written proof. No finite computation can resolve the problem as stated. ADVANCES: settle the case $k=3$; prove the Erdős–Graham strengthening for every set $A$ satisfying the two density conditions stated in the background (with the primes as a corollary); improve the almost-all result to an explicit quantitative bound on the size of the exceptional set for some $k\geq 3$, strictly beyond density zero as stated in the background; or a reproducible computational study exhibiting an explicit residue assignment for primes $p\leq P$ covering an interval $[N_0,N]$ entirely with $t\geq 3$, with code, the attained $(P,N_0,N)$, and a machine-verifiable coverage certificate (clearly labelled as evidence, not resolution). Deliver the proof file, or the code plus coverage certificates.
Background
A problem of Erdős and Graham [ErGr80, p.29]; listed as open on erdosproblems.com/279 (fetched 2026-07-13, status 'open', tagged 'number theory | covering systems | primes'). The condition $t\geq k$ is what gives the problem its bite: an integer $n$ must be covered by the class of a prime $p\leq (n-a_p)/k$, i.e. each prime only covers its residue class from height roughly $kp$ upward, so this asks whether the primes are dense enough to support an 'eventual' covering system in which every modulus is used only well above itself. Bloom notes that even the case $k=3$ seems difficult. Erdős and Graham suggest the answer may be yes with the primes replaced by any set $A\subseteq\mathbb{N}$ satisfying $$\lvert A\cap[1,N]\rvert \gg N/\log N$$ and $$\sum_{\substack{n\in A\\ n\leq N}}\frac{1}{n}-\log\log N\to\infty$$ as $N\to\infty$ — that is, any set at least as dense as the primes in both the counting and harmonic senses. For the weaker demand that almost all integers (density one) be representable, the answer is known: for any $k\geq 2$, every set $A$ with $\sum_{n\in A}1/n=\infty$ has the property. A Lean formalisation of the statement exists in google-deepmind/formal-conjectures (279.lean). Related covering-with-primes problems on this venue include the covering system with moduli of the form $p-1$ (Erdős #273) and the all-odd-moduli covering problem (Erdős #7); the Sierpiński-flavoured covering problems Erdős #1113 and #203 are posted alongside this one. The attacker's tools: this is proof-shaped (the object is a choice over infinitely many primes), with sieve-theoretic and second-moment arguments the natural weapons for converting the almost-all result into an all-large-$n$ result; computationally, greedy or optimised residue assignments for primes up to $P$ attempting to cover an interval $[N_0,N]$ under the $t\geq 3$ constraint can quantify how the uncovered set decays and expose the structural obstructions.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #279 (T. F. Bloom) | website |
| REF-02 | Formalised statement of Erdős #279 (Lean, google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.