Problem Statement
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}$. Let $H(n)$ be the largest $u$ such that there is a sequence of integers $d_1<\cdots < d_u$ all dividing $n$ with $d_{i+1}\equiv 1\pmod{d_i}$.
Estimate $h(n)$ and $H(n)$. Is it true that $H(n)/h(n)\to \infty$ for almost all $n$?
Estimate $h(n)$ and $H(n)$. Is it true that $H(n)/h(n)\to \infty$ for almost all $n$?
Categories:
Number Theory Divisors
Progress
Erdős writes it is 'easy to see' that $h(n)\to \infty$ for almost all $n$ (which is proved in the comments by van Doorn), and believed he could show that the normal order of $h(n)$ is $\log_*(n)$ (the iterated logarithm).See also [695].
Source: erdosproblems.com/696 | Last verified: January 16, 2026