Simplifying $\sum_{i=1}^n{\lfloor \frac{n}{i} \rfloor}$?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.