Erdős problem 414 — live audit and an exact \(10^{10}\) frontier certificate
Accessed 2026-07-28. The full problem is not solved here. The new output is an exact finite theorem: every pair of starting values \(1\leq m,n\leq 10^{10}\) has coalescing orbits under \(T(x)=x+\tau(x)\).
Claim labels used below are the requested ones:
- (a) elementary-rigorous;
- (b) rigorous modulo the named theorem/source;
- (c) plausible or structural but unverified;
- (d) computational-only (finite, exact, and reproducible here).
0. Mandatory live-page audit
The live page was fetched through the Bright Data browser, including its linked discussion thread and its LaTeX-source view. Direct fetches through the ordinary web client returned HTTP 403, as anticipated.
Verbatim live statement
Let $h_1(n)=h(n)=n+\tau(n)$ (where $\tau(n)$ counts the number of divisors of $n$) and $h_k(n)=h(h_{k-1}(n))$. Is it true, for any $m,n$, there exist $i$ and $j$ such that $h_i(m)=h_j(n)$?
Live-page facts, all (d: externally observed metadata):
- Problem 414 says OPEN and says it
was last edited 16 November 2025.
- It shows 0 claimed proofs.
- “Currently working on this problem” is None.
- “Interested in collaborating” is None.
- The page attributes the question to Spiro, says Erdős and Graham believed
the answer was yes, and points to Problems 412 and 413.
- It lists one comment, a formalised statement, and OEIS A064491 as a
possible related sequence.
- The one linked
discussion comment, posted by deepakbal on 31 October 2025, only identifies A064491 as the orbit beginning at 1; the page says it was updated in response. It makes no proof claim.
Therefore none of the mandatory stop conditions applied.
1. Literature audit
- Original source, verified. The page citation
[ErGr80,p.82]is
Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory, Monographie de L'Enseignement Mathématique 28 (1980). I downloaded the UCSD scan and visually checked printed page 82. It gives this iteration with \(d(n)\) for the divisor count, attributes the question to C. Spiro [Spi (77)], says the answer appeared certain to be yes, but says the existence of barriers was much more doubtful. It also reports that Erdős and Selfridge believed any barrier beyond 24 would have to be extremely large. The bibliography identifies [Spi (77)] as a personal communication, not a paper. These are source reports, not theorems (b: verified primary-source attribution).
- OEIS metadata, verified.
A064491 is \(1,2,4,7,9,12,\ldots\), with \(a(1)=1\) and \(a(r+1)=a(r)+\tau(a(r))\). Its reference field says that Spiro proposed the problem at the 1977 West Coast Number Theory Meeting and records both the coalescence question and a separate parity question (d: database observation). OEIS supplies data, not a proof of coalescence.
- Directly relevant current preprint, verified. Exact-phrase and
formula searches found Eric Li, “Square-Annular Dynamics and Coalescence Frontiers for \(n+\tau(n)\)”, arXiv:2606.17926 (submitted 16 June 2026). The actual arXiv paper, not merely a search snippet, explicitly says it does not solve the problem. It proves the graph/frontier and square-annular reductions used below, gives \(R(X)\leq\log X+2\gamma+O(X^{-1/4})\), obtains static exit-set estimates, and isolates dynamic synchronization/square gates as the missing input. Its sharper first-moment statement explicitly assumes an unproved hypothesis \(H_{\rm QE}\) (b: claims of the named preprint; the analytic estimates are not used in this finite certificate). Its illustrative exact table stops at \(k=12\).
- Searches for the exact strings
n+d(n),n+tau(n), Spiro, coalescence,
and the divisor-successor graph across ordinary web search, arXiv, Semantic Scholar-indexed results, zbMATH-indexed results, and the references surfaced by OEIS found no other source specifically advancing this map. That is an honest search miss, not a proof that no such literature exists (c).
The June 2026 preprint is newer than the live page's last-edit date and is not listed there.
2. Elementary finite-frontier lemma
Let \(T(n)=n+\tau(n)\), and let \(\Gamma\) be the undirected graph with the positive integers as vertices and an edge between \(n\) and \(T(n)\).
Lemma (square frontier) (a). Put \(N=k^2\), and define
Then
Every connected component of \(\Gamma\) that meets \([1,N-1]\) also meets \(F_N\). Consequently, if all members of \(F_N\) are in one component, then every integer in \([1,N-1]\) is in that component.
Proof (a). The elementary divisor pairing bound is \(\tau(x)<2\sqrt{x}\). If \(m\leq(k-1)^2\), then
so such an \(m\) cannot cross \(N=k^2\). Every crossing start therefore has \(m=N-j\) with \(1\leq j\leq2k-2\). It crosses exactly when \(\tau(N-j)\geq j\), and its landing point is the displayed value.
For the component assertion, start at any \(x<N\) in the component. Because \(T(y)>y\), its forward orbit is strictly increasing and unbounded. At its first crossing of \(N\), the landing point belongs to both that component and \(F_N\). Thus every component visible below \(N\) is represented in \(F_N\). If \(F_N\) represents only one component, all the visible components are that component. \(\square\)
For this increasing functional graph, two vertices lie in the same undirected component if and only if their forward orbits eventually meet: this is immediate on each edge \(x--T(x)\) and is preserved along a finite undirected path (a).
3. The exact certificate at \(N=10^{10}\)
Take
The checker exactly factors every integer in
This is 6,400,969 consecutive integers. It enumerates the complete square frontier and follows every distinct frontier orbit until it meets the reference orbit beginning at \(N+1\) (d).
Complete active-deficit table
The following is the exact list of all \(j\) with \(1\leq j\leq199998\) and \(\tau(N-j)\geq j\) (d):
| \(j\) | \(\tau(N-j)\) | landing offset \(r=\tau(N-j)-j\) | |---:|---:|---:| | 1 | 48 | 47 | | 2 | 16 | 14 | | 3 | 4 | 1 | | 4 | 48 | 44 | | 5 | 8 | 3 | | 6 | 16 | 10 | | 7 | 8 | 1 | | 8 | 16 | 8 | | 9 | 12 | 3 | | 10 | 80 | 70 | | 12 | 24 | 12 | | 16 | 160 | 144 | | 19 | 24 | 5 | | 20 | 24 | 4 | | 25 | 96 | 71 | | 28 | 72 | 44 | | 30 | 32 | 2 | | 32 | 36 | 4 | | 36 | 72 | 36 | | 46 | 48 | 2 | | 64 | 224 | 160 | | 100 | 432 | 332 | | 172 | 480 | 308 | | 256 | 288 | 32 |
Thus the complete set of 19 distinct frontier offsets is
and \(F_N=N+E\) (d).
Exact orbit joins
The reference orbit starts at \(N+1\), with reference index 0. For every offset \(r\in E\), the table gives the number of \(T\)-steps from \(N+r\) to its first point on that reference orbit (d).
| \(r\) | steps | first common value | reference index | |---:|---:|---:|---:| | 1 | 0 | 10000000001 | 0 | | 2 | 235746 | 10006200970 | 459660 | | 3 | 6 | 10000000081 | 5 | | 4 | 235746 | 10006200970 | 459660 | | 5 | 1 | 10000000013 | 2 | | 8 | 235736 | 10006200970 | 459660 | | 10 | 235745 | 10006200970 | 459660 | | 12 | 235737 | 10006200970 | 459660 | | 14 | 235749 | 10006200970 | 459660 | | 32 | 235730 | 10006200970 | 459660 | | 36 | 235737 | 10006200970 | 459660 | | 44 | 235737 | 10006200970 | 459660 | | 47 | 3 | 10000000081 | 5 | | 70 | 235750 | 10006200970 | 459660 | | 71 | 1 | 10000000081 | 5 | | 144 | 235731 | 10006200970 | 459660 | | 160 | 235731 | 10006200970 | 459660 | | 308 | 235729 | 10006200970 | 459660 | | 332 | 235728 | 10006200970 | 459660 |
The only square on the reference segment is reached at reference index 459659:
Its divisor count is \(\tau(10006200961)=(2+1)(2+1)=9\), so its next iterate is precisely the common meeting value \(10006200970\) (a)+(d). This is the parity-changing bridge: \(\tau(x)\) is odd exactly at squares, so opposite-parity orbit segments cannot merge without one of them visiting a square (a).
The endpoint computation proves that all integers below \(N\) are in one component by the frontier lemma. The checker separately follows \(N\) itself for 19 steps and finds the reference-orbit value \(10000000305\) (reference index 22) (d). Hence:
Finite theorem (a+d). For every \(1\leq m,n\leq10^{10}\), there are \(a,b\geq0\) such that \(T^a(m)=T^b(n)\). Applying \(T\) once more if either exponent is zero gives positive indices in the live page's \(h_1,h_2,\ldots\) convention.
This is a finite theorem only; it does not establish a uniform statement for arbitrary starts.
4. Reproduction and independent checks
The standalone checker is erdos414_wave9f_reverify.py. Run:
python3 runs/erdos414_wave9f_reverify.py
It uses only the Python standard library. Its computational kernel is:
def segmented_tau(low, high, primes):
remaining = array("Q", range(low, high + 1))
tau = array("H", [1]) * (high - low + 1)
for p in primes:
for i in range((-low) % p, len(tau), p):
q, e = remaining[i], 0
while q % p == 0:
q //= p
e += 1
remaining[i] = q
tau[i] *= e + 1
for i, q in enumerate(remaining):
if q > 1:
tau[i] *= 2
return tau
active = []
for j in range(1, 2*K - 1):
d = tau_at(N-j)
if d >= j:
active.append((j, d, d-j))
reference = {}
x = N + 1
while x <= HIGH:
reference[x] = len(reference)
x += tau_at(x)
for r in sorted({d-j for j, d, _ in active}):
x = N + r
while x not in reference:
x += tau_at(x)
assert x <= HIGH
The full checker adds the following safeguards (d):
- an Eratosthenes sieve through \(\lfloor\sqrt{10006200970}\rfloor\);
- direct segmented factorisation of all 6,400,969 required integers;
- an independent single-number trial-division implementation checked at
1,563 regularly spaced values and every concise certificate value;
- exact assertions for all 24 active deficits, 19 frontier endpoints,
join lengths, join values, the square bridge, and the extra start \(N\);
- canonical SHA-256 hashes of the complete divisor-count segment and all
orbit transitions used by the certificate.
Observed clean run:
PASS: exact square-frontier certificate verified
K=100000, N=K^2=10000000000
factored interval=[9999800002,10006200970] (6400969 consecutive integers)
prime_count_through_sqrt(HIGH)=9594, max_tau_on_interval=1600
active_deficits=24; frontier_endpoints=19
bridge=10006200961=100031^2=(67*1493)^2, tau(bridge)=9
tau_segment_sha256=fd56abe319505672a6bb5322016dd2ee99f3be05be6245738b015a07bd0f6287
transition_sha256=44dfbe8bdff64fc7554040fae7b4f872cbb4c33b4810aad2ea5ccdec27d04d9b
CERTIFIED: every pair 1 <= m,n <= 10000000000 has coalescing T-orbits.
On this VM the final run took 13.95 wall seconds and 109,880 KiB peak RSS (d).
5. Exact remaining obstruction
For general \(k\), let
The original problem is equivalent to proving that \(F_{k^2}\) lies in a single component for arbitrarily large \(k\) (a):
- arbitrarily large such \(k\) cover every fixed initial interval by the
frontier lemma;
- if the whole graph is connected, every such frontier is already in one
component.
The finite calculation supplies this property at \(k=100000\), not at arbitrarily large \(k\). Static bounds on the number of frontier points do not force their two parity streams to merge. The exact missing ingredient for this route is a uniform square-hitting/dynamic synchronization lemma: one must force the relevant propagated frontier orbits to visit a square and then prove the resulting branches actually meet (a: reduction; c: no such uniform lemma is known here). Li's preprint isolates the same issue through dynamic annular widths and square gates; its simplest fixed deficit gate would involve primes represented by \(x^2-2\), a Bunyakovsky-type problem (b: route-specific statement from the preprint).
A larger one-off finite certificate is computationally feasible but cannot remove this quantifier. The present exact factor window cost 14 seconds and 110 MiB. A window of roughly 60 million integers near \(10^{12}\) would cost on the order of 1 GiB and a few core-minutes with this Python implementation (c: engineering extrapolation, not run). No finite extension, however large, proves that the required square bridge recurs arbitrarily far out.
PARTIAL: Exact frontier computation proves coalescence for every pair of starts at most 10^10; the open uniform step is to force single-component square frontiers for arbitrarily large k.