---

Claim. The answer to the first question of Problem 673 is yes: $G(n)\to\infty$ for almost all $n$, that is, for every $C$ the integers with $G(n)>C$ have density $1$. Erdős posed the question at the 1978 Luminy Journées Arithmétiques ([Er79e], Astérisque 61, 1979, pp. 73--74, where the sum is written $g(n)$; carded at erdos_1979_unconventional_problems_number_theory_asterisque) and recalled it in the 1982 survey carded at erdos_1982_my_favourite_problems_which_recently_have, Chapter II, section 6, printed p. 66, where he writes the sum as $Q(n)$ and says: "It is trivial that $Q(n)\to\infty$ for almost all $n$." The same passage withdraws his earlier belief that the divergence would imply his conjecture on consecutive divisors $d_i<d_{i+1}<2d_i$, says he hopes to prove that $Q(n)/\tau(n)$ has a distribution function, which "should follow from our work with Tenenbaum", and judges the stronger statement $Q(n)>\tau(n)/2$ for almost all $n$ almost certainly false; a note on printed p. 67, added after the paper was completed, says that he and Tenenbaum proved in July 1981, at the number theory meeting in Budapest, that $Q(n)/\tau(n)$ has a continuous distribution function. The survey gives no proof of the divergence. The site records the argument, observed by Terence Tao: if $m>1$ divides $n$, each divisor $d$ of $n/m$ is followed in the ordered list of divisors of $n$ by a divisor at most $dm$, so the term $d_i/d_{i+1}$ at $d$ is at least $1/m$ and

$$\frac{\tau(n/m)}{m}\le G(n)\le\tau(n);$$

for even $n$ this gives $\tau(n)/4\le G(n)\le\tau(n)$. The divergence follows: given $\varepsilon>0$, choose $B$ so that the integers with no prime factor $p\le B$, whose density is $\prod_{p\le B}(1-1/p)$, have density at most $\varepsilon$; an $n$ with a prime factor $p\le B$ has $G(n)\ge\tau(n/p)/p\ge\tau(n)/(2B)$, since $\tau(n/p)\ge\tau(n)/2$ when $p\mid n$, and $\tau(n)\to\infty$ for almost all $n$, so for every $C$ the integers with $G(n)\le C$ have upper density at most $\varepsilon$, for every $\varepsilon$. The lower bound needs $m>1$, since at $m=1$ it would read $\tau(n)\le G(n)$, which is false; the site's display allows any divisor $m$. The site records Tao's suggestion that the conjecture was a slip that Erdős corrected a year later into Problem 448.

Covers. The first question only: $G(n)\to\infty$ on a set of density $1$. It gives no asymptotic formula for $\sum_{n\le X}G(n)$, the second question, which Erdős and Tenenbaum answered in 1983 (their claim page); the growth of the average, which Erdős's original list called easy, follows from Tao's lower bound or from their formula.

Depends on. No page of this wiki.

Acceptance. Thomas Bloom, the site's curator, marks the problem proved, records Tao's bounds and cites the 1982 remark on the problem page. Erdős's survey asserts the divergence without argument and Tao's observation is a site remark; a refereed argument is Erdős and Tenenbaum's bound $G(n)\ge\tau(n)/(2P^-(n))$, $P^-(n)$ the least prime factor of $n$, on p. 127 of their 1983 paper (their claim page). The Lean development in Boris Alexeev's repository whose theorem G_tendsToInfinityAlmostAll proves the divergence, through tao_lower_bound with the hypothesis $m>1$, names Erdős and Tenenbaum as informal authors and is linked from their claim page, which records this corpus's build of it as formalized evidence for their result. The claim is accepted on the curator's documented acceptance of an elementary argument stated in full on the site.