Do all orbits of $n\mapsto n+\tau(n)$ eventually merge into one sequence? (Erdős #414)
Statement
Let $\tau(n)$ denote the number of divisors of $n$, and define $h(n)=n+\tau(n)$. Iterate it: $h_1(n)=h(n)$ and $h_k(n)=h(h_{k-1}(n))$. Is it true that for every pair of positive integers $m,n$ there exist indices $i,j$ with $h_i(m)=h_j(n)$? Equivalently: do the forward orbits of the map $n\mapsto n+\tau(n)$ all eventually coincide, so that there is (eventually) only one possible trajectory?
Acceptance. FULLY RESOLVES: a complete proof that for every $m,n$ there exist $i,j$ with $h_i(m)=h_j(n)$ (a machine-checkable Lean/Coq proof preferred, otherwise a full written proof with every step) — OR a disproof exhibiting two explicit starting values whose orbits are shown to never meet, with a proof (e.g. a growth or congruence invariant that keeps the two orbits permanently disjoint). ADVANCES: a reproducible computation certifying that all starting values $1\le k\le N$ have orbits that eventually coincide, for a new record $N$ strictly larger than any bound stated in this background, delivered with the search program and an explicit certificate listing each orbit's merge point; OR a proof that the orbits merge for a structured infinite family of starting pairs; OR a rigorous lower bound on the density of integers whose orbit provably joins the A064491 trajectory. Deliver the proof file, or the orbit-merging search code plus the attained $N$ and the per-orbit merge certificate.
Background
Asked by Spiro and recorded by Erdős and Graham [ErGr80, p.82]; Erdős and Graham believed the answer is yes. The map $n\mapsto n+\tau(n)$ is strictly increasing, so each starting value generates a single increasing orbit; the conjecture asserts that any two such orbits eventually run into each other and continue identically, i.e. there is essentially one eventual sequence. The orbit started from $1$ is catalogued as OEIS A064491 ($a(1)=1$, $a(n+1)=a(n)+\tau(a(n))$), so a natural strong form is that every orbit eventually joins A064491. Erdős and Graham note that the same merging question can be posed for iterates of many other arithmetic functions; the closely related Erdős #412 and #413 (erdosproblems.com/412, erdosproblems.com/413) ask analogous questions for other maps. The problem carries no cash prize. A Lean formalisation exists in the Google DeepMind Formal Conjectures project. Listed as open on erdosproblems.com/414 (fetched 2026-07-13, status 'open', tagged 'number theory | iterated functions'). Attacker's tool: exhaustive orbit computation — compute the $h$-orbit of every starting value up to a large bound $N$, record where each orbit first meets a previously-seen orbit, and certify that all of them collapse onto a single trajectory up to a record height; complemented by density/heuristic arguments on how often two increasing orbits are forced to share a value.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #414 (T. F. Bloom) | website |
| REF-02 | OEIS A064491 — a(1)=1, a(n+1)=a(n)+τ(a(n)) (iterating n↦n+number of divisors) | website |
| REF-03 | Lean formalisation — Erdős #414 (Google DeepMind Formal Conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.