Simplifying $\sum_{i=1}^n{\lfloor \frac{n}{i} \rfloor}$? In a few programming contexts, I've come across code along these lines:
total = 0
for i from 1 to n
    total := total + n / i

Where the division here is integer division. Mathematically, this boils down to evaluating
$$\sum_{i = 1}^{n}\left\lfloor\, n \over i\,\right\rfloor.$$
This is upper-bounded by $n H_{n}$ and lower-bounded by $nH_{n} - n$ using the standard inequalities for $\texttt{floor}$'s, but that upper bound likely has a large gap to the true value.
Is there a way to either get an exact value for this summation or find some simpler function it's asymptotically equivalent to?
 A: For exact computation, a simplification begins with the observation
$$ \sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor 
= \sum_{i,j} [1 \leq i] [1 \leq j] [ij \leq n] 1$$
where $[P]$ is the Iverson bracket: it is $1$ if $P$ is true, and $0$ if false.
Anyways, using the symmetry, you can break this down to
$$ \sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor 
= -\lfloor \sqrt{n} \rfloor^2  + 2 \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} \left\lfloor \frac{n}{i} \right\rfloor  $$
This form is better for making rough estimates too, since the roundoff error is a much smaller proportion of the summands.
A: See OES sequence A006218 and Dirichlet divisor problem.  Asymptotically we have 
$$a(n) = n (\log n + 2 \gamma - 1) + O(n^\theta)$$
where the optimal value of $\theta$ is an unsolved problem: the best result given on that MathWorld page is  $\theta = 131/416$, due to Huxley in 2003.
A: Your sum is also equal to $\sum_{i=1}^n \tau(i)$. Notice that if we were able to calculate this sum really fast we would also be able to determine whether $n$ is prime really fast, so calculating your sum is not very easy.
