Erdős Problem #696 — Let $h(n)$ be the largest $\ell$ such that there is a sequence of primes $p_1<\cdots < p_\ell$ all dividing $n$ with $p_{i+1}\equiv 1\pmod{p_i}$.

Erdős Problem $696$ asks whether the longest chain of arbitrary divisors is asymptotically much longer than the corresponding chain of prime divisors. Erdős proposed divergence of this ratio and conjectured that the prime-chain length has normal order $\log_* n$.

Known results

• Wouter van Doorn proved that $h(n)\to\infty$ for almost all $n$.
• An earlier argument claimed $h(n)\gg\log_* n$ and $H(n)\ll\log_* n$ for almost all $n$.

Claimed precise asymptotics (date not stated)

David Turturean’s write-up claims, for all but $o(x)$ integers $n\le x$, that $h(n)=(1/2+o(1))\log_* n$, $H(n)=(1+o(1))\log_* n$, and $H(n)/h(n)\to2$. A Lean formalization is provided, but it treats Siegel–Walfisz, Brun–Titchmarsh, and Mertens’ theorem as axiomatized lemmas; independent mathematical verification is not recorded.

Current status (as of March 2026): The original divergence conjecture has a claimed counterexample and a formalized write-up, but the precise asymptotics and resulting resolution remain unverified.