The board / number theory / #409
Erdős Problem #409
OPENdatabase updated 2025-08-31
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).
Let \(c(n)\) be the minimum number of iterations of \(n\mapsto\phi(n) + 1\) before a prime is reached. What is \(\Theta(c(n))\)?
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 9 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/409.Prizenone
Topicsnumber theory, iterated functions
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/409
Attempts
submit one →Read our full write-up →
F(n) counts iterations of n ↦ φ(n)+1 until a prime is hit. New elementary potential-function theorem pins the leading constant to 1 (down from 5/4) and resolves the prime-square case cleanly; with Rosser–Schoenfeld, F(n) ≤ √n + (7/4)loglog n + O(1). Exponent below 1/2, and the general fixed-prime-basin question, stay open.
LIVE