The key is to count integers with a given number of prime factors: if $\omega(n)=\sum_{p|n}1$ and $\Omega(n)=\sum_{p^a|n,\,a\ge1}1$, then $2^{\omega(n)}\le\tau(n)\le2^{\Omega(n)}$ and there are results that control the number of integers with a given value of $\omega(n)$, or of $\Omega(n)$. The simplest one of them is the Hardy-Ramanujan theorem: there are absolute constants $A$ and $B$ such that

$$\#\{n\le x: \omega(n)=r\}\le\frac{Ax}{\log x}\frac{(\log\log x+B)^{r-1}}{(r-1)!}\tag{*}$$ for all $x\ge3$ and $r\ge1$.

There are also lower bounds for certain ranges of $r$ and $x$ that are harder to obtain (due to Sathe-Selberg, see the chapter "The Selberg-Delange method" in Tenenbaum's book "Introduction to Analytic and Probabilistic Number Theory").

So here is a way to implement (*) in order to bound your sum from above. First, we need a technical trick: Every $n$ can be written in a unique way as $n=ab$, where $a$ is square-free and $b$ is square-full (i.e. $p|n\Rightarrow p^2|n$). Now, we have that

$$
\begin{align}\sum_{n\le x}\min(d(n),M) & \le \sum_{\substack{b\le x\\\ b\,\text{square-full}}} d(b) \sum_{\substack{a\le x/b \\\ a\,\text{square-free}}}\min(d(a),M) \\\
&\le \sum_{\substack{b\le x\\\ b\,\text{square-full}}} d(b) \sum_{a\le x/b}\min(2^{\omega(a)},M)\\\
&=\sum_{\substack{b\le x\\\ b\,\text{square-full}}} d(b) \sum_{r\ge0} \min(2^{r},M)\#\{a\le x/b:\omega(a)=r\}
\end{align}
$$
So you can insert (*) to control this sum when $b\le\sqrt{x}$. When $b>\sqrt{x}$, apply the trivial bound

$$\sum_{r\ge0} \min(2^{r},M)\#\{a\le x/b:\omega(a)=r\}\le\sum_{a\le x/b}d(a)\ll\frac{x\log(x/b)}{b}$$

and note that $$\sum_{b\le y}d(b)\le\sum_{k^2l^3\le y}d(k^2l^3)\ll\sqrt{y}\log y,$$

so that

$$\sum_{\substack{\sqrt{x} \le b\le x \\\ b\,\text{square-full} }} d(b)\sum_{r\ge0}\min(2^r,M)\#\{a\le x/b:\omega(a)=r\}\ll\sqrt{x}\log^2x,$$

by partial summation.

This method will give you an upper bound of the right order of magnitude for all $M$. For the lower bound, you could use that $d(n)\ge 2^{\omega(n)}$ and insert the Sathe-Selberg result (here you need to assume that $M\le(\log x)^{10}$, which is OK; the case $M\ge (\log x)^{10}$ follows by the case $M=(\log x)^{10}$). This would give you lower bounds of matching order essentially for all $M$. You could even get asymptotics but the error term will be weak.

An instructive remark here is that if $M=x$ (i.e. we have the full divisor sum), then this method suggests that

$$\sum_{n\le x}d(n)\approx \frac{x}{\log x}\sum_{r\ge1}\frac{(2\log\log x)^{r-1}}{(r-1)!}.$$

This sum is dominated by $r\approx2\log\log x$. And indeed, this is the case (the contribution of $r$ different from $2\log\log x$ can be bounded by (*)). So for $M\ge(\log x)^{\log 4}$, then your sum is asymptotic to the full divisor sum. However, when $M\le(\log x)^{\log 4-\epsilon}$, then it starts getting smaller, dominated by $r\approx \log M/\log 2$.

firstsum, i.e., is asymptotically $\sum_{n\leq x} d(n)$, for $x$ large enough. $\endgroup$ – kodlu Apr 3 '12 at 23:56