4
$\begingroup$

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

$\endgroup$
9
  • 5
    $\begingroup$ Hold up; are you talking about integer division or normal division? $\endgroup$
    – plshelp
    Oct 2 '20 at 16:02
  • $\begingroup$ Relevant link: math.stackexchange.com/questions/487401/… $\endgroup$
    – integrator
    Oct 2 '20 at 16:06
  • 4
    $\begingroup$ @plshelp it's integer division $\endgroup$
    – Loc Truong
    Oct 2 '20 at 16:14
  • $\begingroup$ @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. $\endgroup$
    – Loc Truong
    Oct 2 '20 at 16:17
  • $\begingroup$ @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. $\endgroup$
    – Loc Truong
    Oct 2 '20 at 16:24
7
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.