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

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

• StackOverflow?. – martin Sep 3 '14 at 8:31
• 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. – Isomorphism Sep 3 '14 at 8:39

## 1 Answer

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$$ • 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$$ – r.e.s. Sep 5 '14 at 14:11
• Thanks for your comments, I've edited the answer with your sugestions. – Esteban Crespi Sep 5 '14 at 14:19
• Thanks a lot for explanation. I was struggling to get this. – Shashikant Sep 6 '14 at 12:45