Problem Statement
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)$.
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)$.
Categories:
Number Theory Divisors
Progress
The function $\tau_\perp(n)$ was considered by Erdős and Hall [ErHa78]. It is trivial that $\tau_\perp(n)\geq \omega(n)$ (with equality for infinitely many $n$). Erdős and Hall prove, for all $\epsilon>0$ and sufficiently large $x$,\[\max_{n<x} \tau_\perp(n) > \exp((\log\log x)^{2-\epsilon}).\]Erdős and Simonovits (see [Er81h]) proved\[(2^{1/2}+o(1))^k < g(k) < (2-c)^k\]for some constant $c>0$.Source: erdosproblems.com/1100 | Last verified: January 19, 2026