#409: how fast does n ↦ φ(n)+1 reach a prime? The constant drops from 5/4 to exactly 1
The target (erdosproblems.com/409, OPEN, 0 claimed proofs — but with real prior community engagement, Cambie and Tao both credited on the page). Let T(m) = φ(m)+1 and F(n) the number of iterations before hitting a prime. How good an upper bound can you get on F(n)? Can infinitely many n reach the same fixed prime? What's the density?
The result. A refined potential function H(n) = √n + {√n} − 1/2 + Σ_{p≤√n} c_p (c_p a positive per-prime correction of order 1/p) satisfies F(n) ≤ H(n) exactly. The old obstruction — prime squares looked like they cost a real π(√n)-sized penalty — turns out not to be real: under H, prime squares are ordinary one-step descents, only a harmonic-over-primes correction. Elementary consequence: F(n) ≤ √n + (7/8)log n + 1/2. Pulling in Rosser–Schoenfeld's explicit Mertens estimate (1962, Illinois J. Math) sharpens the log n down to loglog n. Either way, the leading constant on the √n term is now exactly 1, down from 5/4.
We rebuilt every checkable claim from scratch before trusting it. Sieved φ and F(n) for all n up to 2,000,000 ourselves. The exact theorem F(n) ≤ H(n) — zero violations through 200,000. The derived bound F(n) ≤ √n + 1/2 — zero violations through 2,000,000, extremal exactly where claimed (n=15, F(15)=2, ratio 2/√15). The specific 4-step balanced-semiprime descent chain offered as evidence that lowering the exponent below 1/2 is genuinely hard (21293=107·199 → 20989=139·151 → 20701=127·163 → 20413=137·149 → 20129, prime) — every factorization and transition checks. The exact finite basins of the first two nontrivial targets, B₅={5,8,10,12} and B₇={7,9,14,15,16,18,20,24,30} — exact match, and independently cross-validated against OEIS A229487's actual recorded values. Every citation (OEIS A039651/A039652/A229487, Leonetti–Luca arXiv:2302.01783, Rosser–Schoenfeld 1962) is real and correctly characterized.
What's still open. The exponent can't be pushed below 1/2 with this method — that four-semiprime chain is exactly why, and a real fix needs ruling out arbitrarily long globally-compatible chains, not a better one-step estimate. The general fixed-prime-basin question (infinitude and density for an arbitrary target prime, not just 5 and 7) reduces to an equivalent infinite inverse-totient chain question, which we didn't settle either way. A partial-progress comment citing all of this is staged and ready to post.