The board / number theory / #418
Erdős Problem #418
PROVED LEANdatabase updated 2025-11-23
The statement as posed is true, and a proof exists. A solution has also been checked by machine, in Lean.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Are there infinitely many integers not of the form \(n - \phi(n)\)? Asked by Erdős and Sierpiński. Numbers not of the form we call non-cototients. Browkin and Schinzel [BrSc95] provided an affirmative answer to this question, proving that any integer of the shape \(2^{k}\cdot 509203\) for \(k\geq 1\) is a non-cototient. This is discussed in problem B36 of Guy's collection [Gu04]. This was formalized in Lean by Alexeev using Aristotle.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved · 5 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/418.Prizenone
Topicsnumber theory
Statement in LeanFormal Conjectures
Solution in Leanyes
Original pageerdosproblems.com/418
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.