Erdős Problem #696

Erdős Problem 696: prime chains and divisor chains

Statement and claim.

Let $h(n)$ be the longest increasing chain of prime divisors $p_1,\ldots,p_h$ of $n$ satisfying $p_i\mid p_{i+1}-1$. Define $H(n)$ in the same way with arbitrary positive divisors. We prove, for almost all $n$, \[ h(n)\asymp H(n)\asymp\log_* n,\qquad H(n)/h(n)\leq18. \tag{1} \] In particular the proposed almost-everywhere divergence of the ratio is false. This is a reconstruction of the coarse resolution reported at https://www.erdosproblems.com/696 and its forum, using the prime-successor method in the manuscript hosted at https://github.com/davidturturean/erdos-696. That manuscript attributes its stronger estimates to work with GPT-5.5. No new resolution or sharp normal-order constant is claimed here.

External analytic inputs.

We use the classical Siegel--Walfisz theorem in the following fixed-exponent form: for coprime $a,q$, uniformly for $q\leq\log t$, \[ \pi(t;q,a)=\frac{\operatorname{Li}(t)}{\varphi(q)} +O(t e^{-c\sqrt{\log t}}). \tag{2} \] See A. Walfisz, Zur additiven Zahlentheorie. II, Math. Z. 40 $1936$, 592--607; the cited manuscript states and applies the same uniform input. We also use the elementary classical bounds $\sum_{p\leq z}\log p=O(z)$ and $\sum_p1/p=\infty$. All other probability, counting, and tower estimates are given below.

Few short successor steps in a typical divisor chain.

Call a pair bad if $d\geq Y$, $d<e<\exp(\sqrt d)$, and $e\equiv1\pmod d$. Then $\gcd(d,e)=1$. For fixed $d$, writing $e=1+jd$ gives \[ \sum_{\substack{d<e<\exp(\sqrt d)\\e\equiv1\ (d)}}\frac1{de} \leq\frac1{d^2} \sum_{1\leq j\leq \exp(\sqrt d)/d}\frac1j \ll d^{-3/2}. \] The number of $n\leq x$ divisible by both members of any bad pair is therefore, by a union bound, \[ \leq x\sum_{d\geq Y}\sum_e\frac1{de}\ll xY^{-1/2}. \tag{3} \] For every other $n$, consecutive chain terms above $Y$ satisfy $d_{i+1}\geq f(d_i)$, where $f(t)=\exp(\sqrt t)$. For all sufficiently large $t$, \[ f(f(t))=\exp\left(\exp(\sqrt t/2)\right)\geq\exp(t). \] Define $T_0=e$, $T_{j+1}=\exp(T_j)$, and let $L=\min\{j\geq0:x\leq T_j\}$. This differs from any usual convention for $\log_*x$ by at most a fixed constant. Every two chain steps above $Y$ raise the tower level by at least one. There are at most $2L+O(1)$ such terms, and at most $Y$ terms below $Y$. Taking $Y=\lfloor\sqrt L\rfloor$, we obtain \[ H(n)\leq3L \quad\hbox{for all but }o(x)\hbox{ integers }n\leq x. \tag{4} \]

Enough prime successors in a very large window.

For large $y$, put \[ Z(y)=\exp(\exp y),\qquad F(y)=\exp(\exp(y^2)). \] For every prime $p\leq y$, partial summation in $2$ gives, uniformly in $p$, \[ \sum_{\substack{Z(y)<q\leq F(y)\\q\ {\rm prime}\\q\equiv1\ (p)}} \frac1q =\frac{y^2-y}{p-1}+O\left(e^{-c'\sqrt{\log Z(y)}}\right) \geq y/3. \tag{5} \] Indeed, the modulus condition holds throughout the interval. The integrated error is bounded by a constant times $\int_{\sqrt{\log Z(y)}}^\infty u e^{-cu}\,du$, and the main integral is $(\log\log F(y)-\log\log Z(y))/(p-1)$. Thus no constant in $5$ depends on the chosen prime $p$.

Independent prime choices and transfer to integers.

Let $y_0=L$, $y_{j+1}=F(y_j)$, and $K=\lfloor L/5\rfloor$. Consider independent Bernoulli variables indexed by primes $q\leq y_K$, with success probability $1/q$. With probability tending to one, there is a successful prime $p_0\leq L$, since the probability of none is $\prod_{p\leq L}(1-1/p)\longrightarrow0$. Having chosen $p_j\leq y_j$, seek a successful prime \[ Z(y_j)<p_{j+1}\leq y_{j+1},\qquad p_{j+1}\equiv1\pmod{p_j}. \] The window is disjoint from every window previously inspected. Conditional on all previous choices, $5$ shows that the probability of failure is at most \[ \prod_q(1-1/q)\leq\exp\left(-\sum_q1/q\right) \leq e^{-y_j/3}\leq e^{-L/3}. \] A union bound over $K$ stages now gives a prime chain of length $K+1\geq L/6$, with probability $1-o(1)$.

The size of the prime cutoff matters for transferring this model to uniform integers $n\leq x$. Let $r_0=\min\{r:L\leq T_r\}=o(L)$. For large $y$, $y^2\leq e^y$, so $F(y)\leq\exp(\exp(\exp y))$. Inductively, \[ y_K\leq T_{r_0+3K}\leq T_{L-3}<\log\log x \] for all sufficiently large $x$; the last inequality uses $x>T_{L-1}$. Set $Q=\prod_{p\leq y_K}p$. The classical bound quoted above gives \[ Q\leq\exp(O(y_K))\leq(\log x)^{O(1)}=o(x). \] On a uniformly random residue modulo $Q$, the divisibility events for its primes are exactly the independent model, by the Chinese remainder theorem. For every event depending on that residue, its probability on $\{1,\ldots,\lfloor x\rfloor\}$ differs by $O(Q/x)=o(1)$. Consequently \[ h(n)\geq L/6 \quad\hbox{for all but }o(x)\hbox{ integers }n\leq x. \tag{6} \]

Conclusion and scope.

Combining $4$, $6$, and $h(n)\leq H(n)$ gives $H(n)/h(n)\leq18$ outside $o(x)$ exceptions up to $x$. After discarding the $O(\sqrt x)$ integers below $\sqrt x$, the tower ranks of $n$ and $x$ differ by at most a constant. Thus $4$--$6$ also prove the two order-of-growth assertions in $1$. This settles the stated coarse estimation and ratio question, relative to $2$. It does not reproduce the sharper constants discussed in the cited manuscript.

Completion estimate.

COMPLETION: 100%

Erdős Problem #696

FORMAL RESTATEMENT

Let $n\in\mathbb{N}$ with $n\ge 1$.

• Define $h(n)$ to be the maximum integer $\ell\ge 0$ for which there exist distinct primes \[p_1<p_2<\cdots<p_\ell\] such that $p_i\mid n$ for all $i$ and $p_{i+1}\equiv 1\pmod{p_i}$ for all $1\le i<\ell$. (If $n=1$, then $h(1)=0$.)
• Define $H(n)$ to be the maximum integer $u\ge 1$ for which there exist integers \[1\le d_1<d_2<\cdots<d_u\] such that $d_i\mid n$ for all $i$ and $d_{i+1}\equiv 1\pmod{d_i}$ for all $1\le i<u$. (Note $1\mid n$, so $H(n)\ge 1$ always.)

Tasks:

1. Give meaningful upper/lower bounds ("estimates") for $h(n)$ and $H(n)$ in terms of $n$ and standard arithmetic functions.
2. Decide whether $H(n)/h(n)\to\infty$ for almost all $n$ (natural density $1$).

QUICK LITERATURE/CONTEXT CHECK

The problem statement in the source file says Erdős wrote that $h(n)\to\infty$ for almost all $n$ and believed the normal order is $\log_* n$ (iterated logarithm). The ErdosProblems forum threads summarize this context.(For example, the ErdosProblems discussion page for #696 and the related #695 thread.) I did not find (in a quick search) any claim that the full "$H(n)/h(n)\to\infty$ a.a.s." statement has been resolved as of late 2025.

ATTACK PLAN

• Upper bounds: any chain forces rapid growth of the terms, and the terms must all divide $n$, yielding bounds in terms of $\log n$, $\omega(n)$ (distinct primes), and $\tau(n)$ (divisor count).
• Lower bounds / constructions: if $\operatorname{lcm}(1,2,\dots,m)\mid n$ then the explicit chain $1,2,\dots,m$ gives $H(n)\ge m$.
• "Almost all" questions: relate $H(n)$ to the largest $m$ with $\operatorname{lcm}(1,\dots,m)\mid n$, and relate $h(n)$ to prime factors in "Pratt-tree"-type congruence chains. I only pursue rigorous elementary bounds here.

WORK

Lemma 696.1 (basic monotonicity and trivial bounds). For all $n\ge 1$, \[0\le h(n)\le H(n),\qquad h(n)\le \omega(n),\qquad H(n)\le \tau(n),\] where $\omega(n)$ is the number of distinct prime factors of $n$ and $\tau(n)$ is the number of positive divisors of $n$.

Proof. A prime chain as in the definition of $h(n)$ is in particular a divisor chain (all primes are divisors), so $h(n)\le H(n)$. In such a chain the primes are distinct and divide $n$, so its length is at most the number of distinct prime divisors: $h(n)\le\omega(n)$. Finally, a divisor chain uses distinct positive divisors of $n$, hence has length at most $\tau(n)$. $\square$

Lemma 696.2 (a uniform upper bound on $h(n)$ from forced growth). Let $\ell\ge 2$ and let $p_1<p_2<\cdots<p_\ell$ be primes with $p_{i+1}\equiv 1\pmod{p_i}$ for all $i<\ell$. Then

1. $p_2\ge 3$ and for every $i\ge 2$ one has $p_{i+1}\ge 2p_i+1>2p_i$.
2. Consequently, for every $i\ge 2$ we have $p_i\ge 3\cdot 2^{i-2}$.
3. Consequently, the product of the primes satisfies \[\prod_{i=1}^{\ell} p_i\ \ge\ 2\cdot 3^{\ell-1}\cdot 2^{(\ell-1)(\ell-2)/2}. \] In particular, if all these primes divide $n$ (hence their product divides $n$) then \[h(n)\le 3+\sqrt{2\log_2 n}. \]

   Proof. $1$ Since $p_1$ is prime, either $p_1=2$ or $p_1\ge 3$. In either case $p_2>p_1$ and $p_2\equiv 1\pmod{p_1}$, so $p_2\ge 3$. Now fix $i\ge 2$. Then $p_i\ge 3$ is odd. Writing $p_{i+1}=1+k p_i$ for some integer $k\ge 1$, the parity of $p_{i+1}$ is the parity of $1+k$ because $p_i$ is odd. For $p_{i+1}$ to be an odd prime, we must have $k$ even, hence $k\ge 2$. Therefore $p_{i+1}=1+k p_i\ge 1+2p_i$.

   $2$ From $1$, $p_2\ge 3$ and $p_{i+1}>2p_i$ for all $i\ge 2$. By induction, for $i\ge 2$, $p_i>2^{i-2}p_2\ge 3\cdot 2^{i-2}$.

   $3$ Multiply the bound in $2$ for $i=2,3,\dots,\ell$ and include $p_1\ge 2$: \[ \prod_{i=1}^{\ell}p_i\ge 2\cdot \prod_{i=2}^{\ell}\left(3\cdot 2^{i-2}\right) =2\cdot 3^{\ell-1}\cdot 2^{\sum_{i=2}^{\ell}(i-2)} =2\cdot 3^{\ell-1}\cdot 2^{(\ell-1)(\ell-2)/2}. \] If the chain primes all divide $n$, then the left-hand side divides $n$, so taking $\log_2$ and discarding the nonnegative $(\ell-1)\log_2 3$ term gives $\tfrac{(\ell-1)(\ell-2)}{2}\le \log_2 n$, hence $\ell\le 3+\sqrt{2\log_2 n}$. $\square$

   Lemma 696.3 (explicit lower bound for $H(n)$ via $\operatorname{lcm}(1,\dots,m)$). Let $m\ge 1$ and $n\ge 1$ be integers. If $\operatorname{lcm}(1,2,\dots,m)\mid n$, then $H(n)\ge m$.

   Proof. If $\operatorname{lcm}(1,\dots,m)\mid n$, then every integer $d\in\{1,2,\dots,m\}$ divides $n$. Consider the divisor chain \[d_1=1<d_2=2<\cdots<d_m=m. \] For each $1\le t<m$ we have $d_{t+1}=t+1\equiv 1\pmod{t}$ because $(t+1)-1=t$ is divisible by $t$. Hence this is a valid chain in the definition of $H(n)$ of length $m$, proving $H(n)\ge m$. $\square$

   FAST REALITY CHECK (computation). I brute-forced $h(n)$ and $H(n)$ for $2\le n\le 200$ by dynamic programming over prime divisors (for $h$) and over all divisors (for $H$). Results:

   • For every $2\le n\le 200$, one has $H(n)>h(n)$.
   • The maximum values observed on $2\le n\le 200$ were $\max h(n)=3$ (e.g. $n=42$ has chain $2,3,7$) and $\max H(n)=6$ (e.g. $n=60$ has chain $1,2,3,4,5,6$).
   • The largest observed ratio was $H(n)/h(n)=3$ (e.g. $n=180$ has $h(180)=2$ and $H(180)=6$).

   VERIFICATION

   • Lemma 696.2: the key parity step uses only that $p_i$ is odd for $i\ge 2$; checked separately that $p_2\ge 3$ always.
   • Lemma 696.3: checked that the congruence $t+1\equiv 1\pmod t$ holds for all $t\ge 1$ and that each $t\mid n$ follows from the $\operatorname{lcm}$ hypothesis.
   • Edge cases: $n=1$ gives $h(1)=0$ and $H(1)=1$ (only divisor is $1$), consistent with definitions.

   FINAL

   UNRESOLVED.
   1. (i) Strongest proved partial results here:
      • Uniform upper bound $h(n)\le 3+\sqrt{2\log_2 n}$ (Lemma 696.2).
      • Construction: if $\operatorname{lcm}(1,\dots,m)\mid n$ then $H(n)\ge m$ (Lemma 696.3), giving along the subsequence $n=\operatorname{lcm}(1,\dots,m)$ that $H(n)\ge m$ while $h(n)\ll \sqrt{\log n}$.
   2. (ii) First gap: prove any nontrivial normal-order lower bound for $H(n)$ or $h(n)$ beyond these elementary inequalities, strong enough to decide whether $H(n)/h(n)\to\infty$ for almost all $n$.
   3. (iii) Top 3 next moves:
      1. Relate $H(n)$ to $m(n):=\max\{m: \operatorname{lcm}(1,\dots,m)\mid n\}$ and estimate the normal order of $m(n)$.
      2. For $h(n)$, study the directed graph on prime divisors of $n$ with edges $p\to q$ if $q\equiv 1\pmod p$; attempt to show typical $n$ has a long directed path (e.g. of length $\gg \log_* n$).
      3. Computationally sample $h(n),H(n)$ for large random $n$ (say up to $10^{12}$) and track empirical growth rates and correlations with small prime power divisibility.
   4. (iv) Minimal counterexample structure (to $H(n)/h(n)\to\infty$ a.a.s.): one would need a positive-density set of $n$ with unusually small divisor-consecutive structure (small $m(n)$), but still with $h(n)$ not too small; i.e. integers missing long runs $1,2,\dots,m\mid n$ while still containing relatively long prime congruence chains.