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:

1. 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.

2. 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).

• Hold up; are you talking about integer division or normal division? Oct 2 '20 at 16:02
• Relevant link: math.stackexchange.com/questions/487401/… Oct 2 '20 at 16:06
• @plshelp it's integer division Oct 2 '20 at 16:14
• @eru-cs thanks, but I need to know how to come up with the second formula, which only needs to loop until sqrt of n. Oct 2 '20 at 16:17
• @eru-cs please keep your answer, it's the one that I'm looking for. But I need the proof for that one to understand the solution. Otherwise it's just copy-paste stuff. Oct 2 '20 at 16:24

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.

Following what eru-cs wrote you get a nice and fast formula, but it is mathematically quite difficult. If you are not that good at maths (and it is hard) and can afford a bit more execution time:

If k < $$n^{1/2}$$ then you can calculate easily the smallest and largest i such that n/i = k using integer division, and from that you can count how many such i there are; multiply by k and you get the sum of n/i for all these i.

You add up these sums, then you find for which i you didn’t add n/i and you add those. Done.

You can optimise this a bit, because the largest i such that n/i = k is one less than the smallest i such that n/i = k+1. And since calculating these sums is more complex, you might do the sums for $$k < (n/2)^{1/2}$$ for example.