Erdős Problem #467

Erdős Problem 467 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/467

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/467.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/467.tex.

1) FORMAL RESTATEMENT.

Fix a (large) real $x$; for concreteness interpret $x$ as a large integer and quantify over integers $n$ with $1\le n<x$. For each prime $p\le x$ choose a residue class $a_p\in\{0,1,\dots,p-1\}$. Partition the primes $\{p\le x\}$ into a disjoint union $A\sqcup B$ with $A,B\ne\emptyset$. The desired property is: \[ \forall n<x\ \exists p\in A,\ q\in B\ \text{s.t.}\ n\equiv a_p\pmod p\ \text{and}\ n\equiv a_q\pmod q. \]

2) QUICK LITERATURE/CONTEXT CHECK.

The statement notes that [ErGr80] is missing quantifiers and that the above is an interpretation. I will work only with the explicitly stated formulation.

3) ATTACK PLAN.

• First, rewrite the condition in a way that separates the roles of $A$ and $B$.
• Prove a necessary counting condition on any single collection of prime-residue classes that covers all $n<x$.
• Perform a small-$x$ exhaustive search to sanity-check the statement and to see where obstructions appear.

4) WORK.

Lemma 467.1 (equivalence to two separate coverings). The condition \[ \forall n<x\ \exists p\in A\ \text{s.t.}\ n\equiv a_p\pmod p\quad\text{and}\quad \exists q\in B\ \text{s.t.}\ n\equiv a_q\pmod q \] is equivalent to the pair of covering statements: \[ \forall n<x:\ n\in \bigcup_{p\in A}\{m: m\equiv a_p\ (\mathrm{mod}\ p)\}\quad\text{and}\quad \forall n<x:\ n\in \bigcup_{q\in B}\{m: m\equiv a_q\ (\mathrm{mod}\ q)\}. \]

Proof. The original condition says: for each $n<x$ there is at least one congruence from the $A$-family that $n$ satisfies, and at least one congruence from the $B$-family that $n$ satisfies. This is exactly the statement that $n$ lies in the union of the $A$-progressions and in the union of the $B$-progressions. $\square$

Lemma 467.2 (counting necessary condition for a single cover). Let $P$ be a set of primes and let $a_p$ be a residue class modulo $p$ for each $p\in P$. Suppose that for every integer $n$ with $1\le n<x$ there exists some $p\in P$ with $n\equiv a_p\pmod p$. Then \[ \sum_{p\in P}\Big\lceil\frac{x-1}{p}\Big\rceil\ \ge\ x-1. \] In particular, \[ \sum_{p\in P}\frac{1}{p}\ \ge\ 1-\frac{|P|}{x-1}. \]

Proof. For each $p\in P$, the arithmetic progression $\{n: 1\le n<x,\ n\equiv a_p\ (\mathrm{mod}\ p)\}$ contains at most $\lceil (x-1)/p\rceil$ integers. The union of these sets covers the $x-1$ integers $1,2,\dots,x-1$, hence by the union bound \[ x-1\le \sum_{p\in P}\Big|\{n:1\le n<x,\ n\equiv a_p\ (\mathrm{mod}\ p)\}\Big|\le \sum_{p\in P}\Big\lceil\frac{x-1}{p}\Big\rceil. \] Since $\lceil (x-1)/p\rceil\le (x-1)/p+1$, rearranging yields $\sum_{p\in P} 1/p\ge 1-|P|/(x-1)$. $\square$

Corollary 467.3 (a necessary condition on $x$). If the conclusion of the problem holds for a given $x$, then necessarily \[ \sum_{p\le x}\frac1p\ \ge\ 2 - O\Big(\frac{\pi(x)}{x}\Big), \] since by Lemma 467.1 each of the two sets $A$ and $B$ must separately satisfy Lemma 467.2.

Proof. Apply Lemma 467.2 to $P=A$ and $P=B$ and add the resulting inequalities. $\square$

FAST REALITY CHECK (small $x$ exhaustive search).

I wrote an exact backtracking search for the interpreted statement (covering all integers $1\le n<x$). For each $x\le 20$ it searched over all partitions $A\sqcup B$ of the primes $\le x$ and, for each side, searched over all residue choices to see whether that side covers all $n<x$.

The script returned no solutions for $5\le x\le 20$:

x=5: none
x=6: none
x=7: none
x=8: none
x=9: none
x=10: none
x=11: none
x=12: none
x=13: none
x=14: none
x=15: none
x=16: none
x=17: none
x=18: none
x=19: none
x=20: none

This is consistent with Corollary 467.3: numerically,

x=10:  sum_{p<=x} 1/p = 1.176190476190476
x=20:  sum_{p<=x} 1/p = 1.4554777523817768
x=30:  sum_{p<=x} 1/p = 1.5334387718720317
x=100: sum_{p<=x} 1/p = 1.8028172010488706
x=1000:sum_{p<=x} 1/p = 2.198080127175088

so for $x\le 100$ the harmonic-sum necessary condition "total $\ge 2$" is not even met.

5) VERIFICATION.

• Lemma 467.1 is a direct rewriting; no hidden assumptions.
• Lemma 467.2 uses only the trivial union bound and the fact that one residue class mod $p$ hits at most $\lceil (x-1)/p\rceil$ integers in $[1,x)$.
• The computational check is exhaustive for each tested $x$ because it tries all partitions and all residues (via backtracking) for each side.

6) FINAL. UNRESOLVED

(i) Strongest proved partial result. The problem is equivalent to constructing two disjoint prime-modulus covering systems of the finite interval $\{1,2,\dots,x-1\}$ (Lemma 467.1). Any such cover by primes $P$ must satisfy the counting condition $\sum_{p\in P} \lceil(x-1)/p\rceil\ge x-1$ (Lemma 467.2), forcing in particular $\sum_{p\in P}1/p\gtrsim 1$. Exhaustive search finds no examples for $x\le 20$.

(ii) First gap (crisp). Construct, for all sufficiently large $x$, explicit residues $a_p$ and a partition $A\sqcup B$ such that each of $A$ and $B$ individually covers all integers $1\le n<x$ by the single residue class assigned to each prime.

(iii) Top 3 next moves.

1. Attempt an explicit constructive cover for one side using small primes (to cover most residues) plus a controlled use of larger primes to mop up remaining uncovered $n$; then repeat disjointly for the other side.
2. Reformulate as a finite set-cover problem: each prime $p$ contributes one translate of the partition of $[1,x)$ into $p$ residue classes; seek two disjoint families whose unions both cover. Try a greedy algorithm and attempt to prove it terminates when $\sum_{p\le x}1/p$ is large enough.
3. Push computation with optimized search/ILP for moderate $x$ (say $x$ in the hundreds) to locate the smallest $x$ where a solution exists (if any), guided by the harmonic-sum constraint.

(iv) Minimal counterexample structure. A minimal failing $x$ would be one for which every assignment of residues and every partition $A\sqcup B$ leaves some $n<x$ uncovered by $A$ or uncovered by $B$. By Lemma 467.1, it is enough to understand obstructions to a single prime-residue cover of $[1,x)$ using a given subset of primes.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

1) FORMAL RESTATEMENT.

Fix a (large) real $x$; for concreteness interpret $x$ as a large integer and quantify over integers $n$ with $1\le n<x$. For each prime $p\le x$ choose a residue class $a_p\in\{0,1,\dots,p-1\}$. Partition the primes $\{p\le x\}$ into a disjoint union $A\sqcup B$ with $A,B\ne\emptyset$. The desired property is: \[ \forall n<x\ \exists p\in A,\ q\in B\ \text{s.t.}\ n\equiv a_p\pmod p\ \text{and}\ n\equiv a_q\pmod q. \]

2) QUICK LITERATURE/CONTEXT CHECK.

The statement notes that [ErGr80] is missing quantifiers and that the above is an interpretation. I will work only with the explicitly stated formulation.

3) ATTACK PLAN.

• First, rewrite the condition in a way that separates the roles of $A$ and $B$.
• Prove a necessary counting condition on any single collection of prime-residue classes that covers all $n<x$.
• Perform a small-$x$ exhaustive search to sanity-check the statement and to see where obstructions appear.

4) WORK.

Lemma 467.1 (equivalence to two separate coverings). The condition \[ \forall n<x\ \exists p\in A\ \text{s.t.}\ n\equiv a_p\pmod p\quad\text{and}\quad \exists q\in B\ \text{s.t.}\ n\equiv a_q\pmod q \] is equivalent to the pair of covering statements: \[ \forall n<x:\ n\in \bigcup_{p\in A}\{m: m\equiv a_p\ (\mathrm{mod}\ p)\}\quad\text{and}\quad \forall n<x:\ n\in \bigcup_{q\in B}\{m: m\equiv a_q\ (\mathrm{mod}\ q)\}. \]

Proof. The original condition says: for each $n<x$ there is at least one congruence from the $A$-family that $n$ satisfies, and at least one congruence from the $B$-family that $n$ satisfies. This is exactly the statement that $n$ lies in the union of the $A$-progressions and in the union of the $B$-progressions. $\square$

Lemma 467.2 (counting necessary condition for a single cover). Let $P$ be a set of primes and let $a_p$ be a residue class modulo $p$ for each $p\in P$. Suppose that for every integer $n$ with $1\le n<x$ there exists some $p\in P$ with $n\equiv a_p\pmod p$. Then \[ \sum_{p\in P}\Big\lceil\frac{x-1}{p}\Big\rceil\ \ge\ x-1. \] In particular, \[ \sum_{p\in P}\frac{1}{p}\ \ge\ 1-\frac{|P|}{x-1}. \]

Proof. For each $p\in P$, the arithmetic progression $\{n: 1\le n<x,\ n\equiv a_p\ (\mathrm{mod}\ p)\}$ contains at most $\lceil (x-1)/p\rceil$ integers. The union of these sets covers the $x-1$ integers $1,2,\dots,x-1$, hence by the union bound \[ x-1\le \sum_{p\in P}\Big|\{n:1\le n<x,\ n\equiv a_p\ (\mathrm{mod}\ p)\}\Big|\le \sum_{p\in P}\Big\lceil\frac{x-1}{p}\Big\rceil. \] Since $\lceil (x-1)/p\rceil\le (x-1)/p+1$, rearranging yields $\sum_{p\in P} 1/p\ge 1-|P|/(x-1)$. $\square$

Corollary 467.3 (a necessary condition on $x$). If the conclusion of the problem holds for a given $x$, then necessarily \[ \sum_{p\le x}\frac1p\ \ge\ 2 - O\Big(\frac{\pi(x)}{x}\Big), \] since by Lemma 467.1 each of the two sets $A$ and $B$ must separately satisfy Lemma 467.2.

Proof. Apply Lemma 467.2 to $P=A$ and $P=B$ and add the resulting inequalities. $\square$

FAST REALITY CHECK (small $x$ exhaustive search).

I wrote an exact backtracking search for the interpreted statement (covering all integers $1\le n<x$). For each $x\le 20$ it searched over all partitions $A\sqcup B$ of the primes $\le x$ and, for each side, searched over all residue choices to see whether that side covers all $n<x$.

The script returned no solutions for $5\le x\le 20$:

x=5: none
x=6: none
x=7: none
x=8: none
x=9: none
x=10: none
x=11: none
x=12: none
x=13: none
x=14: none
x=15: none
x=16: none
x=17: none
x=18: none
x=19: none
x=20: none

This is consistent with Corollary 467.3: numerically,

x=10:  sum_{p<=x} 1/p = 1.176190476190476
x=20:  sum_{p<=x} 1/p = 1.4554777523817768
x=30:  sum_{p<=x} 1/p = 1.5334387718720317
x=100: sum_{p<=x} 1/p = 1.8028172010488706
x=1000:sum_{p<=x} 1/p = 2.198080127175088

so for $x\le 100$ the harmonic-sum necessary condition "total $\ge 2$" is not even met.

5) VERIFICATION.

• Lemma 467.1 is a direct rewriting; no hidden assumptions.
• Lemma 467.2 uses only the trivial union bound and the fact that one residue class mod $p$ hits at most $\lceil (x-1)/p\rceil$ integers in $[1,x)$.
• The computational check is exhaustive for each tested $x$ because it tries all partitions and all residues (via backtracking) for each side.

6) FINAL. UNRESOLVED

(i) Strongest proved partial result. The problem is equivalent to constructing two disjoint prime-modulus covering systems of the finite interval $\{1,2,\dots,x-1\}$ (Lemma 467.1). Any such cover by primes $P$ must satisfy the counting condition $\sum_{p\in P} \lceil(x-1)/p\rceil\ge x-1$ (Lemma 467.2), forcing in particular $\sum_{p\in P}1/p\gtrsim 1$. Exhaustive search finds no examples for $x\le 20$.

(ii) First gap (crisp). Construct, for all sufficiently large $x$, explicit residues $a_p$ and a partition $A\sqcup B$ such that each of $A$ and $B$ individually covers all integers $1\le n<x$ by the single residue class assigned to each prime.

(iii) Top 3 next moves.

1. Attempt an explicit constructive cover for one side using small primes (to cover most residues) plus a controlled use of larger primes to mop up remaining uncovered $n$; then repeat disjointly for the other side.
2. Reformulate as a finite set-cover problem: each prime $p$ contributes one translate of the partition of $[1,x)$ into $p$ residue classes; seek two disjoint families whose unions both cover. Try a greedy algorithm and attempt to prove it terminates when $\sum_{p\le x}1/p$ is large enough.
3. Push computation with optimized search/ILP for moderate $x$ (say $x$ in the hundreds) to locate the smallest $x$ where a solution exists (if any), guided by the harmonic-sum constraint.

(iv) Minimal counterexample structure. A minimal failing $x$ would be one for which every assignment of residues and every partition $A\sqcup B$ leaves some $n<x$ uncovered by $A$ or uncovered by $B$. By Lemma 467.1, it is enough to understand obstructions to a single prime-residue cover of $[1,x)$ using a given subset of primes.