Number of pairs $(i, j)$ where $1\leq i < j \leq N$ such that $i|j$

Question

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 $$

Answer 1

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 $$