Erdős Problem #409

Erdős Problem 409: a checked attempt

GPT_6_Astra_Ultra

25 September 2026

Statement and scope

This corrects the earlier GPT-5.2 draft's suggestion that termination itself might fail. Its fixed-depth finiteness argument is retained with proof; no novelty is claimed for the elementary deductions.

Strict descent and an explicit iteration bound

Let $F(n)$ count steps before the first prime, including $F(p)=0$. At any composite term $x\ge4$, put $y=T(x)$. Since $x-y\ge\sqrt x-1\ge\sqrt x/2$, \[ \sqrt x-\sqrt y=\frac{x-y}{\sqrt x+\sqrt y}\ge\frac14. \] Summing this inequality along the strictly decreasing part proves \[ F(n)\le4\sqrt n\qquad(n\ge2),\qquad F(1)=1. \tag{1} \] In particular $F(n)=o(n)$. On the other hand, $F(2p)=1$ for every odd prime $p$, since $\varphi(2p)=p-1$.

Finite levels and exact small basins

For $m>2$, $\varphi(m)$ is even by pairing reduced residues $a$ and $m-a$. Thus $T(m)$ is odd, while $T(1)=T(2)=2$. In particular no even integer larger than two has a predecessor. The complete small totient fibres are \[ \varphi^{-1}(1)=\{1,2\},\quad \varphi^{-1}(2)=\{3,4,6\},\quad \varphi^{-1}(4)=\{5,8,10,12\}. \] These follow either directly from the product formula or by the finite prime-and-exponent list just proved. The parity observation now gives the entire basins \[ B_2=\{1,2\},\quad B_3=\{3,4,6\},\quad B_5=\{5,8,10,12\}. \] All three have density zero, not merely finite depth.

One further example is \[ B_7=\{7,9,14,15,16,18,20,24,30\}. \] Indeed $\varphi^{-1}(6)=\{7,9,14,18\}$ and $\varphi^{-1}(8)=\{15,16,20,24,30\}$. The only new odd value needing predecessors is $15$, but $\varphi(m)=14$ has no solution: its allowable primes are only $2,3$, whose totient factors cannot supply the factor $7$. Every other new predecessor is even and is a leaf. These checks prove exhaustion of this basin.

The divisor-sum variant

Remaining gap

Completion rate estimate: 35%.

1) FORMAL RESTATEMENT

Define the map $T:\mathbb N\to\mathbb N$ by \[ T(n)=\varphi(n)+1. \]

For $n\ge 1$, define the iteration sequence $n_0=n$ and $n_{j+1}=T(n_j)$. Let $F(n)$ be the least $j\ge 0$ such that $n_j$ is prime. (So if $n$ is prime, $F(n)=0$.)

Questions. (A) How large can $F(n)$ be (as a function of $n$)? (B) Can infinitely many $n$ reach the same prime under iteration? (C) For a fixed prime $p$, what is the density of $n$ that eventually reach $p$?

2) QUICK LITERATURE/CONTEXT CHECK

I only restate what is in the problem statement.

The statement records: - Cambie notes $F(n)=o(n)$ is trivial, and that $F(n)=1$ infinitely often.

3) ATTACK PLAN

Proof-track (partial): - Prove simple infinite families with small $F(n)$. - Prove finiteness of the set of $n$ reaching a given prime in a fixed number of steps. - Compute $F(n)$ for small $n$ as sanity.

Disproof-track: - Try to find $n$ with large $F(n)$ by computation (small range only).

Chosen path: prove explicit families and a finiteness lemma for fixed-depth preimages; compute $F(n)$ for $n\le 100$.

4) WORK

PHASE 1 — FAST REALITY CHECK (computed)

I computed $F(n)$ for $1\le n\le 100$ by iterating $T(n)=\varphi(n)+1$ until reaching a prime (with a large iteration cap that never bound in this range). The maximum value in this range is \[ \max_{1\le n\le 100} F(n)=4, \] attained at $n=69$ and $n=92$.

Lemma 1 (fixed points). If $p$ is prime, then $T(p)=p$. Hence primes are fixed points of the iteration.

Proof. If $p$ is prime then $\varphi(p)=p-1$, so $T(p)=\varphi(p)+1=(p-1)+1=p$. $\square$

Lemma 2 (an infinite family with $F(n)=1$). If $p$ is an odd prime and $n=2p$, then $T(n)=p$. In particular, $F(2p)=1$ for all odd primes $p$.

Proof. If $p$ is odd prime, $\gcd(2,p)=1$ so $\varphi(2p)=\varphi(2)\varphi(p)=1\cdot(p-1)=p-1$. Therefore $T(2p)=\varphi(2p)+1=(p-1)+1=p$, which is prime. Thus $F(2p)=1$. $\square$

Lemma 3 (finite preimages of a fixed totient value). For any fixed integer $m\ge 1$, the equation $\varphi(n)=m$ has only finitely many integer solutions $n$.

Proof. Suppose $\varphi(n)=m$. Write the prime factorisation of $n$ as $n=\prod_{i=1}^r p_i^{e_i}$. Then \[ \varphi(n)=\prod_{i=1}^r p_i^{e_i-1}(p_i-1)=m. \] In particular, for each prime divisor $p_i$ of $n$, the factor $(p_i-1)$ divides $m$, so $p_i\le m+1$. Also, $p_i^{e_i-1}$ divides $m$, so $e_i-1\le v_{p_i}(m)$, hence $e_i\le v_{p_i}(m)+1$. Thus each $p_i$ must lie in the finite set of primes $\le m+1$, and each exponent $e_i$ is bounded. Therefore there are only finitely many possible $n$.

(Concretely, one can bound the number of possibilities by taking all combinations of these bounded prime powers.) $\square$

Corollary 4 (finite reachability in fixed time). Fix a prime $q$ and an integer $t\ge 1$. Then the set of $n$ such that the iteration reaches $q$ in at most $t$ steps is finite.

Proof. If the iteration reaches $q$ in $t$ steps, then the previous value $n_{t-1}$ satisfies $\varphi(n_{t-1})+1=q$, i.e. $\varphi(n_{t-1})=q-1$. By Lemma 3, there are finitely many possibilities for $n_{t-1}$. Applying the same reasoning backwards $t-1$ times, and using Lemma 3 at each step, gives finiteness of the set of starting points $n$. $\square$

5) VERIFICATION

- Lemma 2 is consistent with computation: e.g. $n=22=2\cdot 11$ gives $T(22)=11$ so $F(22)=1$. - Lemma 3: checked on an example, $\varphi(n)=2$ has solutions $n\in\{3,4,6\}$, which is finite. - Corollary 4 does not rule out infinitely many $n$ reaching $q$ over unbounded time, which matches the open nature of the question.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here. - Infinite family with $F(n)=1$: all $n=2p$ with $p$ odd prime (Lemma 2). - For each fixed depth $t$, only finitely many $n$ can reach a given prime within $t$ steps (Corollary 4). - Computation: $\max_{n\le 100} F(n)=4$.

(ii) Exact first gap. Prove (or disprove) that every $n$ eventually reaches a prime under iteration of $T(n)=\varphi(n)+1$, and obtain nontrivial upper bounds on $F(n)$.

(iii) Top 3 next moves (concrete targets). 1. Study growth/decay of the iterates $n_j$; for composite $m$, $\varphi(m)+1<m$ typically, suggesting descent, but rigorous global descent bounds are needed. 2. For a fixed prime $q$, investigate whether the union over all depths $t$ of the $t$-step preimages can be infinite, and if so estimate its density. 3. Large-scale computation of $F(n)$ for $n$ up to a large bound to guess growth rates and identify potential “hard” starting values.

(iv) What a minimal counterexample would likely look like. A counterexample to “every $n$ reaches a prime” would be a smallest starting value $n$ whose trajectory is either eventually periodic among composite numbers or strictly decreasing to a composite fixed point (none are currently known), avoiding primes indefinitely.