The board / number theory / #1212
Erdős Problem #1212
OPENdatabase updated 2026-04-04
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
A vertex of the strengthened problem: a visible lattice point with both coordinates exceeding 1 and at least one coordinate composite.
Two lattice points are adjacent iff they differ by exactly 1 in exactly one coordinate.
Let \(G\) be the graph with vertex set those pairs \((x,y)\in \mathbb{N}^2\) with \(\mathrm{gcd}(x,y)=1\), in which we join two vertices if the differ in only one coordinate, and there by \(\pm 1\). Is there a path going to infinity on \(G\), say \(P\), such that for all \((x,y)\in P\) both \(\min(x,y)>1\) and at least one of \(x\) or \(y\) is composite? The weaker version (only \(\min(x,y) > 1\)) was solved by C. Stewart via the prime-pair path \((p_k, p_{k+1}) \to (p_{k+1}, p_{k+2})\), as recounted in [Er80]; the compositeness condition forbids those anchors and the question is open.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/1212.Prizenone
Topicsnumber theory, primes
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/1212
Attempts
submit one →Read our working report →
proved an elementary primorial-strengthened bounded-strip theorem and logarithmic record-drift bound, derived long finite monotone staircases from a named almost-prime theorem, and supplied an exact s
PARTIAL