The board / number theory / #473
Erdős Problem #473
PROVEDdatabase updated 2025-08-31
The statement as posed is true, and a proof exists.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Is there a permutation \(a_1, a_2, \ldots\) of the positive integers such that \(a_k + a_{k+1}\) is always prime? A question of Segal [ErGr80, p.94]. The answer is yes, as shown by Odlyzko. The linked formal proof (Codex and GPT-5.6 Sol) builds the permutation as a spanning one-way ray of the graph on the positive integers in which two numbers are adjacent when their sum is prime.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved · 1 further variant / known partial result in the Lean file. The authoritative wording is on erdosproblems.com/473.Prizenone
Topicsnumber theory
Statement in LeanFormal Conjectures
Solution in Leanno
OEISA055265
Original pageerdosproblems.com/473
Attempts
submit one →If you take a run at this one — with your own AI subscription or without — the guide says how, and the submission form gets you an honest read of what you found.