5
$\begingroup$

This is a programming question so I tried like this:

for (int i=1; N/i != 1; i++)
    sum += N/i-1;

I am getting the correct answer. But one solution I saw by somebody which I could not understand which is :

for (int i=1; i<=sqrt(N); i++) 
    sum += N/i;

ans = 2*sum - sqrt(N)*sqrt(N) - N

How this formula can be derived, I am not able to get that. Please help me in this regard.

To explain it in more clear way :

The number of integers in $\{1, ..., N\}$ that are divisible by $i$ (excluding $i$ itself) equals $N/i - 1$.

For example, $N = 5$, there are $5/1$ (i.e. $5$) numbers $(1, 2, 3, 4, 5)$ which are divisible by $1$ and there are $5/2$ (i.e. $2$) numbers $(2, 4)$ which are divisible by $2$

For calculating the total number of pairs, I am adding all the values $(N/i - 1)$ where $i\ge 1$ and $N/i > 1$.

for example,

For N=5, 
    sum = (5/1 - 1) + (5/2 - 1) = 4 + 1 = 5

for N = 6,
    sum = (6/1 - 1) + (6/2 - 1) + (6/3 - 1) = 5 + 2 + 1 = 8

This is giving correct answer. But I saw one solution which is like this :

First it is adding all the values $N/i$ where $1\le i\le \text{sqrt}(N)$.

for example,

For N=6, 
    sum = 6/1 + 6/2 = 6 + 3 = 9

Then it is calculating the answer as:

ans = 2*sum - sqrt(N)*sqrt(N) - N    (*)

    = 2*9 - 2*2 - 6 = 8

NB: In all of the above, the $/$ mark denotes integer division, i.e. $N/i := \left \lfloor \frac{N}{i}\right\rfloor$, and $\text{sqrt}$ denotes integer square root, i.e. $\text{sqrt}(N) = \left \lfloor \sqrt{N} \right\rfloor$.

Can anyone help me how to derive the formula (*)?

EDIT: The mathematical question may be stated as asking how to establish the following identity in the positive integer variable $N$:

$$\sum_{i\ = \ 1..\ \left \lfloor \frac{N}{2}\right\rfloor} \left(\left \lfloor \frac{N}{i}\right\rfloor - 1\right )\ \ =\ \ 2\left( \sum_{i\ =\ 1..\ \left\lfloor\sqrt N \right\rfloor} \left \lfloor \frac{N}{i}\right\rfloor \right)- {\left\lfloor\sqrt N \right\rfloor}^2 - N $$

$\endgroup$
  • $\begingroup$ StackOverflow?. $\endgroup$ – martin Sep 3 '14 at 8:31
  • 2
    $\begingroup$ Would you kindly write the algorithm instead of the code? I suspect many people here would not be able to understand what the code means. But I assure you that they can help you with the other expression if they understand your question. $\endgroup$ – Isomorphism Sep 3 '14 at 8:39
1
$\begingroup$

The number of pairs you look at can be written in more convinient way as: $$ \sum_{i=1}^N \left\lfloor \frac{N}{i} \right \rfloor - N $$ The sum in the left can be seen as the number of points with integral coordinates under the the hyperbola $xy=N$, the colored region in the figure (including the borders).

Now call $A, B, C$ the sets of points with integral coordinates in each of the regions shown in the figure, where the points with integral coordinates lying in $B$ are counted only in $B$. Then by symmetry $\lvert A \rvert = \lvert C \rvert $ and thus the total number of points is given under the hyperbola is given by $$ \lvert A \rvert+\lvert B \rvert+\lvert C \rvert=2(\lvert A \rvert + \lvert B \rvert)- \lvert B \rvert $$ $\lvert A \rvert+\lvert B \rvert$ is given by the sum $$ \sum_{i\le \sqrt{N}} \left\lfloor \frac{N}{i} \right \rfloor $$ and the number of points in $B$ is clearly $$\lfloor \sqrt{N} \rfloor^2$$

So finally the number of pairs is

$$ \sum_{i=1}^N \left\lfloor \frac{N}{i} \right \rfloor - N = 2(\lvert A \rvert + \lvert B \rvert)- \lvert B \rvert-N = 2\sum_{i\le \sqrt{N}} \left\lfloor \frac{N}{i} \right \rfloor -\lfloor \sqrt{N} \rfloor^2 -N $$ enter image description here

$\endgroup$
  • $\begingroup$ There are some typos: the -|A| should be -|B|, and there is a $2$ in the last line. It might be clearer to write $$\sum_{i=1}^N \left\lfloor \frac{N}{i} \right \rfloor - N = |A|+|B|+|C|-N = 2(|A|+|B|)-|B| - N = 2\sum_{i\le \sqrt{N}} \left\lfloor \frac{N}{i} \right \rfloor - \lfloor \sqrt{N} \rfloor^2 - N $$ $\endgroup$ – r.e.s. Sep 5 '14 at 14:11
  • $\begingroup$ Thanks for your comments, I've edited the answer with your sugestions. $\endgroup$ – Esteban Crespi Sep 5 '14 at 14:19
  • $\begingroup$ Thanks a lot for explanation. I was struggling to get this. $\endgroup$ – Shashikant Sep 6 '14 at 12:45

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.