← All problems

Erdős Problem #696 — Prime and divisor congruence chains

48 years old · traced to

Let h(n)h(n) be the largest ℓ\ell such that there is a sequence of primes p1<⋯<pℓp_1<\cdots < p_\ell all dividing nn with pi+1≡1(modpi)p_{i+1}\equiv 1\pmod{p_i}. Let H(n)H(n) be the largest uu such that there is a sequence of integers d1<⋯<dud_1<\cdots < d_u all dividing nn with di+1≡1(moddi)d_{i+1}\equiv 1\pmod{d_i}. Estimate h(n)h(n) and H(n)H(n). Is it true that H(n)/h(n)→∞H(n)/h(n)\to \infty for almost all nn?

References

Progress summary

Refreshed
Open · solution reported

A recent unverified proof claims the conjectured divergence is false: for almost all integers, the ratio approaches two instead.

Erdős Problem 696696 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\log_* n.

Known results

  • Wouter van Doorn proved that h(n)→∞h(n)\to\infty for almost all nn.
  • An earlier argument claimed h(n)≫log⁡∗nh(n)\gg\log_* n and H(n)≪log⁡∗nH(n)\ll\log_* n for almost all nn.

Claimed precise asymptotics (date not stated)

David Turturean’s write-up claims, for all but o(x)o(x) integers n≤xn\le x, that h(n)=(1/2+o(1))log⁡∗nh(n)=(1/2+o(1))\log_* n, H(n)=(1+o(1))log⁡∗nH(n)=(1+o(1))\log_* n, and H(n)/h(n)→2H(n)/h(n)\to2.

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

Sources

Solutions 0

No solutions have been posted yet.