Problem 1100

If $1=d_1<\cdots<d_{\tau(n)}=n$ are the divisors of $n$ , then let $\tau_\perp(n)$ count the number of $i$ for which $(d_i,d_{i+1})=1$ .

Is it true that $\tau_\perp(n)/\omega(n)\to \infty$ for almost all $n$ ? Is it true that

\tau_\perp(n)< \exp((\log n)^{o(1)})

for all $n$ ?

Let

g(k) = \max_{\omega(n)=k}\tau_\perp(n),

where $\omega(n)$ counts the number of distinct prime divisors of $n$ , and $n$ is restricted to squarefree integers. Determine the growth of $g(k)$ .

Source: erdosproblems.com/1100

Number theory
Divisors

Wiki page

Status

Open

No claim settles this problem.

Open on the site (OPEN; page last edited 19 October 2025; accessed 2026-10-07, with two proof claims listed as partial on its proof-claims thread). The frontmatter standing open derives from the claim pages: the accepted partial claim Erdős and Tenenbaum's bounds settles the first two questions (yes and no), and the pending partial claims Korsky's maximal order and Ross's golden-ratio bound bear on the maximal order and on the growth of $g(k)$ ; no full claim is recorded.

Er81h: Erdős, P., Some problems and results on additive and multiplicative number theory. Analytic number theory (Philadelphia, Pa., 1980) (1981), 171-182.
Er85: Erdős, P., Some solved and unsolved problems of mine in number theory. Topics in analytic number theory (Austin, Tex., 1982), Univ. Texas Press, Austin (1985), 59-75; the lower bound (26) and the question (27), cited from the author-archive scan.
ErHa78: Erdős, P. and Hall, R. R., On some unconventional problems on the divisors of integers. J. Austral. Math. Soc. Ser. A (1978), 479-485.
ErTe89: Erdős, P. and Tenenbaum, G., Sur les fonctions arithmétiques liées aux diviseurs consécutifs. J. Number Theory 31 (1989), no. 3, 285-311, DOI 10.1016/0022-314X(89)90075-9; the theorems of its introduction, cited from the author-archive scan.
ChSS13: Chevyrev, I., Searles, D. and Slinko, A., On the number of facets of polytopes representing comparative probability orders. Order 30 (2013), no. 3, 749-761, DOI 10.1007/s11083-012-9274-0; arXiv:1103.3938 (21 March 2011). Definitions 4 and 5, p. 4, and Theorem 3, p. 6, of the arXiv text.

Problem 1100

Status

Proof claims

Discussion