Sum of series (n/1) + (n/2) + (n/3) + (n/4) +…….+ (n/n)

I wonder if there is a formula to calculate the sum of n/1 + n/2 + n/3 + n/4 + ... + 1. (Integer division)

The number n can be as large as 10^12, so a formula or a solution having the time complexity of O(logn) will work.

This is how far I can get:

-
The sum can be described as n * (1 + 1/2 + 1/3 + 1/4 + ... + 1/n). The series inside the parenthese is the Harmonic Progression which has no formula to calculate. So I don't think this can lead to a solution.

-
Playing with some numbers, this is what I get:

11 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
10 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1
9 + 4 + 3 + 2 + 1 + 1 + 1 + 1 + 1
8 + 4 + 2 + 2 + 1 + 1 + 1 + 1
7 + 3 + 2 + 1 + 1 + 1 + 1
6 + 3 + 2 + 1 + 1 + 1
5 + 2 + 1 + 1 + 1
4 + 2 + 1 + 1
3 + 1 + 1
2 + 1
1

So by skipping the number 1s, we can reduce the time by a half. If using a loop to calculate the sum, we only need to loop until n/2. Since the rest contains only number 1s.

I've been trying to come up with a formula to calculate the series that is not 1 + 1 + ... + 1.
Please help if you know the acceptable answer (a formula or a O(logn) solution).

Based on the following observation, you can derive a $O(\sqrt{n})$ time algorithm ( by computing the sum on the right-hand side naively in a $O(\sqrt{n})$-sized loop): (For $n=10^{12}$ this yields $n=10^{6}$ which is enough for say competitive programming sites which usually allow ~10^8 operations)

For any positive integer $n$, Let $k=\lfloor\sqrt{n}\rfloor$:
$$
\sum_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloor = 2\sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor - k^2
$$

This post on Math StackExchange provides a clear visual proof of the equality above.

The following is a proof for the equality above that does not depend on a graph.

All variables below stand for positive integers. Let us fix $n$ and $k=\lfloor\sqrt{n}\rfloor$. For all $i, j\le n$, let
$\delta(i,j)=1$ if $i\cdot j\le n$. $\delta(i,j)=0$ otherwise. In particular,

• $\delta(i,j) = 1$ if $i,j\le k$.

• $\delta(i,j) = 0$ if $i,j\ge k+1$.

Proposition. $\left\lfloor\dfrac{n}{i}\right\rfloor = \displaystyle\sum_{j=1}^n \delta(i,j) $ for all $i$.

Proof. Both sides count the number of positive multiples of $i$ that are smaller than or equal to $n$. $\ \checkmark$

$$\begin{aligned}
\sum_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloor
&= \sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
+ \sum_{i=k+1}^n \left\lfloor\frac{n}{i}\right\rfloor \\
&= \sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
+ \sum_{i=k+1}^n \sum_{j=1}^n \delta(i,j)\\
&= \sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
+ \sum_{i=k+1}^n \sum_{j=1}^k \delta(i,j)\\
&= \sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
+ \sum_{j=1}^k \sum_{i=k+1}^n \delta(i,j)\\
&= \sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
+ \sum_{j=1}^k\left(\sum_{i=1}^n \delta(i,j)-\sum_{i=1}^k \delta(i,j)\right)\\
&= 2\sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
- \sum_{j=1}^k\sum_{i=1}^k \delta(i,j))\\
&= 2\sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
- k^2 \quad \checkmark \\
\end{aligned}$$

The proof above is, basically, a direct translation of the visual proof.

StackExchange Computer Science Q#130728, answer score: 7