---

Claim. Put $T(n)=\phi(n)+1$. Let $F(n)$ be the number of iterations of $T$ needed to reach a prime from $n$, with $F(p)=0$ for a prime $p$, and for a prime $p$ let $B_p$ be the set of positive integers that reach $p$ after zero or more iterations of $T$. The five-page notes Notes on Erdős Problem #409: the forest structure of $n\mapsto\varphi(n)+1$, dated 22 July 2026 (the preprint link, pinned to the commit of 2026-07-22 that uploaded it), state three results on the problem's questions.

First, $F(n)\le5\sqrt n+1$ for every $n\ge1$ (Theorem 1(vii)). The notes derive it from $T(m)\le m-\sqrt m+1$ for composite $m\ge4$, whose least prime factor is at most $\sqrt m$: then $m-T(m)\ge\frac12\sqrt m$, at most $\sqrt{2x}$ composite iterates lie in $(x/2,x]$, and summing over dyadic ranges gives $F(n)\le\sqrt{2n}\,(1-2^{-1/2})^{-1}+O(1)\le5\sqrt n+1$.

Second, every basin $B_p$ of a prime $p<30000$ is finite and was computed exactly (Section 4): $3245$ trees, none truncated at caps of $4\cdot10^4$ nodes and $10^{12}$ values. The search lists, from $p$ upward, the solutions $x$ of $\phi(x)=m-1$ at the root and at every odd node $m$; an even number at least $4$ is not a value of $T$, so even nodes are leaves. The inverse-totient solver is reported validated against brute force for every value up to $2000$, using $n\le2\phi(n)^2$, and the search is the repository's basins.py. Among the results, $B_2=\{1,2\}$, $B_3=\{3,4,6\}$, $B_5=\{5,8,10,12\}$, $B_7=\{7,9,14,15,16,18,20,24,30\}$ and $B_{11}=\{11,22\}$; $B_{13}$ has $31$ elements, height $4$ and largest element $138$, and $B_{61}$ has $57$ elements, height $8$ and largest element $4314$. The largest basin found is $B_{21089}$, with $5557$ elements, and the tallest is $B_{23509}$, of height $20$.

Third, let $p>3$ be a prime with $p\equiv3\pmod4$ (Theorem 2). Then the solutions $n\ne p$ of $T(n)=p$ are $2p$ and the numbers $q^a$ and $2q^a$ with $q$ a prime, $q\equiv3\pmod4$, $a\ge2$ and $q^{a-1}(q-1)=p-1$. If $p-1$ has no such form, then $B_p=\{p,2p\}$, since $2p$ is even and at least $4$ and so is not a value of $T$. The primes $p\le x$ for which $p-1$ has that form number at most $\sqrt{2x}+O(x^{1/3}\log x)$, so for all but a proportion tending to zero of the primes $p\equiv3\pmod4$, exactly two positive integers reach $p$ and the set of those that do has density zero. The proof writes $n=2^bm$ with $m$ odd and uses $v_2(\phi(n))=\max(b-1,0)+\sum_{q\mid m}v_2(q-1)$, which must equal $1$ since $p\equiv3\pmod4$. The notes check the characterization on the $1632$ primes $3<p<30000$ with $p\equiv3\pmod4$: $1620$ have the basin $\{p,2p\}$, and the $12$ exceptions are the primes the characterization predicts.

The forum comment (the discussion link) states the third result, with the count $O(\sqrt x)$, and the second; the first is in the notes only.

Submission note. Posted to the erdosproblems.com forum by the account ankit on 22 July 2026:

Two observations bearing on the finiteness conjecture recorded above (that only finitely many integers reach any fixed prime), plus exhaustive data.

1. For 100% of primes $p \equiv 3 \pmod 4$, exactly two integers ever reach $p$, namely $p$ and $2p$. Sketch: if $\varphi(n) = p-1 \equiv 2 \pmod 4$, write $n = 2^b m$ with $m$ odd; then $v_2(\varphi(n)) = \max(b-1,0) + \sum_{q \mid m} v_2(q-1) = 1$ forces (for $p>3$) either $n \in \{p, 2p\}$ or $n \in \{q^a, 2q^a\}$ with $q \equiv 3 \pmod 4$ prime, $a \geq 2$, $q^{a-1}(q-1) = p-1$. Since $\varphi(n)+1$ is odd for $n \geq 3$, no even number $\geq 4$ has a preimage, so $2p$ is terminal. Hence unless $p - 1 = q^{a-1}(q-1)$ is solvable, the full basin of $p$ is $\{p, 2p\}$; and the number of exceptional $p \leq x$ is $O(\sqrt{x})$, which is $o(\pi(x))$. This proves the conjectured finiteness (and density zero) for a full-density subfamily of primes $\equiv 3 \pmod 4$. Computationally: of the 1632 primes $3 < p < 30000$ with $p \equiv 3 \pmod 4$, exactly 1620 have basin $\{p, 2p\}$, and the 12 exceptions are precisely ${7, 19, 43, 163, 487, 1459, 4423, 6163, 14407, 19183, 22651, 26407}$, matching the characterization.

2. Exhaustive data: for every prime $p < 30000$ the full basin is finite and computed exactly (largest: 5557 elements at $p = 21089$; tallest tree: height 20 at $p = 23509$). Over all $n \leq 10^7$, $\max F(n) = 38$, attained at $n = 7754613$, with decade records $4, 7, 11, 18, 28, 38$ for $n \leq 10^2, \ldots, 10^7$, consistent with $\max_{n \leq x} F(n) \asymp \log x$, and complementing the constructed $F = 67$ examples posted elsewhere in this thread.

3. Two cautions on the conjecture. (a) Dickson's conjecture implies $F$ is unbounded: for each $L$, the forms $q_i = 3^{i-1} 2^{L-i+1} t - 1$ ($1 \leq i \leq L$) and $p = 2^{L+1} t - 3$ form an admissible system, and their simultaneous primality gives $F(3 q_L) = L$ exactly, via $q_{i+1} = (3 q_i + 1)/2$ (verified witnesses through $L = 6$). (b) Empirically, tree growth is a multitype branching process in the type $v_2(m-1)$ (type-1 nodes are sterile by observation 1), and the measured mean-offspring matrix has Perron root $\approx 1.07$ to $1.17$ across scales $10^4$ to $10^7$: marginally supercritical. If the finiteness conjecture holds, it holds near criticality; the alternative reading is that infinite basins exist but are rare.

Full notes with proofs, the exact basin certificates, and verification code: https://github.com/ak56ankit/erdos-409-notes/blob/main/erdos409.pdf . Disclosure per forum rules: this work was done with substantial AI assistance (Claude, Anthropic); I have independently verified the proofs by hand and reproduced all computations myself.

Covers. The three questions of Problem 409, each in part. For the first, how many iterations are needed, the explicit bound $F(n)\le5\sqrt n+1$, against the trivial $o(n)$ that the problem page records; it gives no lower bound and does not determine the order of growth. For the second and third, every prime below $30000$, and every prime $p>3$ with $p\equiv3\pmod4$ for which $p-1$ is not $q^{a-1}(q-1)$ with $q$ a prime, $q\equiv3\pmod4$ and $a\ge2$, which are all but $O(\sqrt x)$ of the primes up to $x$: only finitely many $n$ reach each such prime, and the density of those that do is zero. The primes above $30000$ that are $1\pmod4$ or exceptional are not addressed, and the notes list the second and third questions in full, whether any basin is infinite, as still open.

Claimant and assistance. The notes' byline prints the author as Ankit. They were uploaded on 22 July 2026 to the GitHub repository ak56ankit/erdos-409-notes, with their TeX source, a Markdown version and the code for the computations (the inverse-totient solver e409.py, the basin search basins.py and the checking script verify.py), and were linked the same day from a comment in the problem's erdosproblems.com forum thread by the account ankit. The notes' footnote says that they were prepared with substantial AI assistance (Claude, Anthropic), that every numerical claim was machine-verified with the accompanying code, and that the author verified all proofs by hand and reproduced all computations; the comment repeats the disclosure. The notes call their theorems elementary and possibly folklore, call the ingredients of Theorem 2 classical, and make no priority claim beyond the results being apparently unrecorded for this problem. The comment and the notes also report the maximum $38$ iterations over $n\le10^7$, that Dickson's prime $k$-tuples conjecture would make the number of iterations unbounded, and a Perron root measured for a branching model of the inverse trees; these are outside this claim.

Relation to other claims. Wouter van Doorn's comment of the same day in the same thread (its claim page) gives $F(n)=O(\sqrt n)$ without a constant, from the same inequality for composite $n$; the notes do not mention it. Plasma AI's later research page on the small prime basins, author-recorded and without independent review, gives $F(n)\le4(\sqrt n-\sqrt2)$ for $n\ge2$ and the same five basins of $2,3,5,7,11$, by its own argument; they are pending on its claim page. Plasma AI's claim page on two-element basins records the basin $\{p,2p\}$ for almost every prime, in every residue class, from Theorem 4.1 of Banks, Ford, Luca, Pappalardi and Shparlinski (2005), with at most $C_\delta x/(\log x)^{2-\delta}$ exceptional primes up to $x$. That theorem covers all residue classes with a weaker exception count; the third result here treats only the primes $p\equiv3\pmod4$, with $O(\sqrt x)$ exceptions and an explicit description of them. Both end with the same step: $2p$ is even and at least $4$, so it is not a value of $T$.

Depends on. No page of this wiki.

Standing. Claimed. The results are posted in a forum comment and in notes and code in a public repository; they have no refereed publication and no Lean proof, and the erdosproblems.com page, last edited 20 December 2025, mentions none of them. Plasma AI rederived the argument of Theorem 2, author-recorded and without independent review, and found it correct as stated; that check is coverage, not acceptance. The notes' proof of the bound and the basin computations were not checked here.