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}$ . 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$ ?

Source: erdosproblems.com/696

Number theory
Divisors

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

SOLVED (LEAN). The site records the two-sided bound $\log_* n\ll h(n)\le H(n)\ll\log_* n$ for almost all $n$ , attributing the proofs to GPT 5.5; the bound implies a negative answer to the ratio question. The derived standing, solved and answered, rests on Treasure42's accepted claim, whose argument the site's curator summarized and accepted; Turturean's sharper asymptotics, with the Lean developments the site's qualification refers to, stay a pending claim.

Problem 696

Status

Proof claims

Discussion