tauPlus n (written $\tau^+(n)$) counts the number of $k$ such that $n$ has a divisor in $[2^k, 2^{k+1})$. Equivalently, the number of distinct values $\lfloor \log_2 d \rfloor$ as $d$ ranges over the divisors of $n$: a divisor $d$ lies in $[2^k, 2^{k+1})$ iff Nat.log 2 d = k.

Sanity check: $\tau^+(6) = 3$. Divisors $1, 2, 3, 6$ lie in dyadic blocks $k = 0, 1, 1, 2$, so the distinct blocks are ${0, 1, 2}$. ($\tau(6) = 4$.)

Sanity check: $\tau^+(12) = 4$. Divisors $1, 2, 3, 4, 6, 12$ lie in dyadic blocks $k = 0, 1, 1, 2, 2, 3$, so the distinct blocks are ${0, 1, 2, 3}$. ($\tau(12) = 6$.)

Always $\tau^+(n) \le \tau(n)$: the occupied dyadic blocks are the image of the divisor set under Nat.log 2, and an image has at most as many elements as its source. This is what makes the $\epsilon < 1$ comparison in the problem meaningful.

Let $\tau(n)$ count the divisors of $n$ and $\tau^+(n)$ count the number of $k$ such that $n$ has a divisor in $[2^k, 2^{k+1})$. Is it true that, for all $\epsilon > 0$, $$ \tau^+(n) < \epsilon \cdot \tau(n) $$ for almost all $n$?

This is false, and was disproved by Erdős and Tenenbaum [ErTe81], who showed that in fact the upper density of the set of such $n$ is $\asymp \epsilon^{1-o(1)}$ (where the $o(1)$ in the exponent $\to 0$ as $\epsilon \to 0$). A more precise result was proved by Hall and Tenenbaum [HaTe88] (see Section 4.6), who showed that the upper density is $\ll \epsilon \log(2/\epsilon)$. Hall and Tenenbaum further prove that $\tau^+(n)/\tau(n)$ has a distribution function. Erdős and Graham also asked whether there is a good inequality known for $\sum_{n \leq x} \tau^+(n)$. This was provided by Ford [Fo08] who proved $$ \sum_{n \leq x} \tau^+(n) \asymp x\frac{(\log x)^{1-\alpha}}{(\log\log x)^{3/2}} $$ where $$ \alpha = 1-\frac{1+\log\log 2}{\log 2} = 0.08607\cdots. $$

Quantitative form of the (negative) answer to erdos_448. Erdős and Tenenbaum [ErTe81] showed that the upper density of ${n : \tau^+(n) < \epsilon \cdot \tau(n)}$ is in fact $\asymp \epsilon^{1 - o(1)}$, where the $o(1)$ in the exponent tends to $0$ as $\epsilon \to 0$. Equivalently, $\log(\text{upper density}) / \log \epsilon \to 1$ as $\epsilon \to 0^+$.

A more precise result of Hall and Tenenbaum [HaTe88, §4.6]: the upper density of ${n : \tau^+(n) < \epsilon \cdot \tau(n)}$ is $\ll \epsilon \cdot \log(2/\epsilon)$ as $\epsilon \to 0^+$.

Hall and Tenenbaum [HaTe88] further prove that $\tau^+(n)/\tau(n)$ has a distribution function: there is a function F such that, for every $z$, the set ${n : \tau^+(n)/\tau(n) \le z}$ has density F z.

Erdős and Graham asked whether there is a good inequality for $\sum_{n \le x} \tau^+(n)$. This was answered by Ford [Fo08], who proved $$ \sum_{n \le x} \tau^+(n) \asymp x \cdot \frac{(\log x)^{1 - \alpha}}{(\log\log x)^{3/2}}, $$ where $\alpha = 1 - \frac{1 + \log\log 2}{\log 2} = 0.08607\ldots$.