Erdős Problem #414

Erdős Problem 414: a checked attempt

GPT_6_Astra_Ultra

25 September 2026

Statement and scope

Let $T(n)=n+\tau(n)$, where $\tau(n)$ is the number of positive divisors. Must the forward orbits of any two positive integers eventually meet? Source: https://www.erdosproblems.com/414. We prove common near-linear growth and a subpower bound on the number of different eventual-orbit classes represented by small starts. The assertion that there is only one class remains unresolved here.

The earlier GPT-5.2 draft reported finite merger counts without enough information to certify an infinite-orbit conclusion. We do not use those counts. All bounds below are proved, and no novelty is claimed for them.

An elementary divisor bound

For every $\delta>0$ there is a constant $C_\delta$ such that \[ \tau(m)\le C_\delta m^\delta\quad(m\ge1). \tag{1} \] To prove this from unique factorization, write $m=\prod p^{a_p}$. If $p^\delta\ge2$, then $a+1\le2^a\le p^{\delta a}$ for every $a\ge0$. Only finitely many primes have $p^\delta<2$. For each of those primes, the quantity $(a+1)p^{-\delta a}$ is bounded over $a\ge0$, since exponential decay dominates a linear factor. Multiplying these finitely many bounds gives $1$.

Every orbit has the same logarithmic growth exponent

For a start $n\ge2$, let $x_k=T^{\circ k}(n)$. Since $\tau(m)\ge2$ for $m\ge2$, \[ x_k\ge n+2k. \tag{2} \] Fix $0<\delta<1$. The function $t^{1-\delta}$ is concave, so $1$ gives \[ x_{k+1}^{1-\delta}-x_k^{1-\delta} \le(1-\delta)x_k^{-\delta}(x_{k+1}-x_k) \le(1-\delta)C_\delta. \] Summation proves \[ x_k\le\big(n^{1-\delta}+(1-\delta)C_\delta k\big)^{1/(1-\delta)}. \tag{3} \] In particular, for every $\eta>0$ take $\delta=\eta/(1+\eta)$ to get $x_k=O_{n,\eta}(k^{1+\eta})$. Together with $2$, this yields \[ \lim_{k\to\infty}\frac{\log x_k}{\log k}=1. \tag{4} \] The orbit of one enters two after one step, so it has the same limit. Equal growth exponents do not imply that two integer sequences intersect.

Few classes among small starting values

Define two starting values to be equivalent if their orbits meet. This is an equivalence relation: after meeting they have the same tail, and strict increase makes intersections permanent in this sense. Let $C(X)$ be the number of equivalence classes represented by starts in $[1,X]\cap\mathbb N$, and put \[ D(X)=\max_{1\le t\le2X}\tau(t) \] for integral $X\ge1$. Select one starting value from each of the $C(X)$ different classes. Its orbit strictly increases and eventually exceeds $2X$. If its terms at most $2X$ are $x_0,\ldots,x_{q-1}$, then $x_0\le X$ and each of the first $q$ increments is at most $D(X)$. Thus \[ qD(X)\ge x_q-x_0>X, \] so the orbit supplies more than $X/D(X)$ distinct integers in $[1,2X]$. The selected orbits are disjoint, because any intersection would put two starts in the same class. Counting these integers gives \[ C(X)\frac{X}{D(X)}<2X, \qquad C(X)<2D(X)\ll_\eta X^\eta \quad\hbox{for every fixed }\eta>0. \tag{5} \] Thus the number of classes grows more slowly than every fixed positive power of the cutoff. Formula $5$ does not establish boundedness: an unbounded function such as $\log X$ has the same property. Even a uniform finite bound would still not prove that the bound is one.

Parity and a finite recognition procedure

Pairing divisors $d$ and $m/d$ shows that $\tau(m)$ is odd exactly at squares. Therefore $T$ flips parity exactly when the current term is a square. Parity supplies no invariant separating all even and odd starts; for instance $T(4)=7=T(5)$.

To search for a meeting of two orbits, keep their current terms and advance whichever is smaller, stopping at equality. Because both maps strictly increase, this procedure detects every actual common term after finitely many advances. If the orbits never meet, it runs forever. Failure to find a meeting before any fixed cutoff therefore proves no counterexample.

Remaining gap

Equations $4$--$5$ constrain every orbit and the number of possible classes. They neither force intersections nor furnish an invariant separating a pair of classes. A proof that $C(X)=1$ for every $X$, or a rigorous pair of permanently disjoint orbits, is still missing.

Completion rate estimate: 35%.

FORMAL RESTATEMENT

Let $\tau(n)$ be the number of positive divisors of $n$. Define $$h(n)=n+\tau(n),$$ and iterate by $h_0(n)=n$ and $h_{k+1}(n)=h(h_k(n))$. Question (Spiro): for every $m,n\ge1$, do there exist indices $i,j\ge0$ such that $$h_i(m)=h_j(n)?$$ (Equivalently, do all forward orbits under $h$ intersect?)

QUICK LITERATURE/CONTEXT CHECK

The problem file says Erdős and Graham believed the answer is yes. No external results are used here.

ATTACK PLAN

As in Problem 412, $h(n)>n$ for $n\ge2$, so orbits are strictly increasing and have no cycles. To show all orbits intersect, one would want some contraction/invariant argument; to disprove, one would try to build two disjoint increasing orbits. We develop basic structural lemmas (growth and parity), then do a computational sanity check for many starting values.

WORK

Lemma 414.1 (Uniform drift). For every integer $n\ge2$ we have $\tau(n)\ge2$, hence $h(n)\ge n+2$. Consequently, for all $k\ge0$, $$h_k(n)\ge n+2k,$$ so every orbit diverges.

Proof. If $n\ge2$ then $1$ and $n$ are distinct divisors, so $\tau(n)\ge2$. Thus $h(n)=n+\tau(n)\ge n+2$. Inductively, $h_{k+1}(n)=h(h_k(n))\ge h_k(n)+2$, so $h_k(n)\ge n+2k$. $\square$

Lemma 414.2 ($\tau(n)$ is odd iff $n$ is a square). For $n\ge1$, $\tau(n)$ is odd if and only if $n$ is a perfect square.

Proof. Divisors of $n$ come in pairs $(d,n/d)$. These two divisors are distinct unless $d=n/d$, i.e. $d^2=n$. So the total number of divisors is odd exactly when there is an unpaired divisor, which happens exactly when $n$ is a square. $\square$

Corollary 414.3 (Parity behavior of $h$). If $n$ is not a square, then $\tau(n)$ is even and $h(n)\equiv n\pmod 2$. If $n$ is a square, then $\tau(n)$ is odd and $h(n)\equiv n+1\pmod 2$.

Proof. Immediate from Lemma 414.2. $\square$

FAST REALITY CHECK (exact computations). I precomputed $\tau(t)$ for $t\le 1{,}005{,}000$ by a divisor-count sieve. For each start $2\le s\le 1000$, I iterated $v\mapsto v+\tau(v)$ until the value exceeded $10^6$. Processing starts in increasing order and recording the first time each value appeared, I observed:

• $998$ of the $999$ starts in $2..1000$ hit a value already seen in an earlier start's orbit before exceeding $10^6$.
• The number of distinct terminal values (the first value $>10^6$ reached, or the last value before crossing) among starts $2..1000$ was $677$.

Again, this is only finite evidence: many early mergers happen, but many distinct tails remain by $10^6$.

VERIFICATION

• Lemma 414.1 handles $n=1$ separately: $h(1)=1+\tau(1)=2$, so orbits also increase from $1$.
• Lemma 414.2 is the standard divisor-pairing argument with no hidden assumptions.
• Corollary 414.3 gives a concrete parity rule; note that parity is not preserved, it flips exactly at square terms.

FINAL

UNRESOLVED

(i) Strongest proved partial result: every orbit under $h(n)=n+\tau(n)$ is strictly increasing and satisfies the linear lower bound $h_k(n)\ge n+2k$ (Lemma 414.1). Also, parity flips occur exactly when an iterate hits a square (Lemma 414.2 and Corollary 414.3).

(ii) First gap: prove that all orbits intersect (i.e. the functional graph has a single infinite forward path), or construct two starting values whose increasing $h$-orbits are disjoint.

(iii) Top 3 next moves:

1. Try to prove that every sufficiently large orbit must hit a square (causing parity flips) infinitely often or must enter some constrained subset where merging can be forced.
2. Look for a monotone "Lyapunov" function $L(n)$ that decreases under the map when comparing two orbits, enabling a coupling/merging argument.
3. Extend computation to much larger caps (e.g. $10^8$) and search for two starts whose orbits remain disjoint up to that cap as counterexample candidates.

(iv) Minimal counterexample structure: two integers $m,n$ such that the sets $\{h_k(m)\:k\ge0\}$ and $\{h_k(n)\:k\ge0\}$ are disjoint; since orbits are increasing, such a counterexample would exhibit at least two distinct infinite forward paths in the functional graph of $h$.