Número de pares $(i, j)$ donde $1\leq i < j \leq N$ tal que $i|j$

Question

Esta es una pregunta de programación así que lo intenté así:

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

Estoy recibiendo la respuesta correcta. Pero una solución que vi por alguien que no podía entender que es :

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

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

Cómo se puede derivar esta fórmula, no soy capaz de conseguirlo. Por favor, ayúdenme en este sentido.

Para explicarlo de forma más clara :

El número de enteros en $\{1, ..., N\}$ que son divisibles por $i$ (excluyendo $i$ mismo) es igual a $N/i - 1$ .

Por ejemplo, $N = 5$ Hay $5/1$ (es decir $5$ ) números $(1, 2, 3, 4, 5)$ que son divisibles por $1$ y hay $5/2$ (es decir $2$ ) números $(2, 4)$ que son divisibles por $2$

Para calcular el número total de pares, estoy sumando todos los valores $(N/i - 1)$ donde $i\ge 1$ y $N/i > 1$ .

por ejemplo,

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

Esta es la respuesta correcta. Pero vi una solución que es así:

En primer lugar, se suman todos los valores $N/i$ donde $1\le i\le \text{sqrt}(N)$ .

por ejemplo,

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

Entonces está calculando la respuesta como:

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

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

NB : En todo lo anterior, el $/$ La marca denota división de enteros es decir $N/i := \left \lfloor \frac{N}{i}\right\rfloor$ y $\text{sqrt}$ denota raíz cuadrada entera es decir $\text{sqrt}(N) = \left \lfloor \sqrt{N} \right\rfloor$ .

¿Alguien puede ayudarme a derivar la fórmula (*)?

EDITAR : La pregunta matemática puede plantearse como si se tratara de establecer la siguiente identidad en la variable entera positiva $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

El número de pares que se mira puede escribirse de forma más convincente como $$ \sum_{i=1}^N \left\lfloor \frac{N}{i} \right \rfloor - N $$ La suma de la izquierda puede verse como el número de puntos con coordenadas integrales bajo la hipérbola $xy=N$ La región coloreada en la figura (incluyendo los bordes).

Ahora llama $A, B, C$ los conjuntos de puntos con coordenadas integrales en cada una de las regiones mostradas en la figura, donde los puntos con coordenadas integrales que se encuentran en $B$ se cuentan sólo en $B$ . Entonces, por simetría $\lvert A \rvert = \lvert C \rvert $ y por lo tanto el número total de puntos está dado bajo la hipérbola está dado por $$ \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$ viene dada por la suma $$ \sum_{i\le \sqrt{N}} \left\lfloor \frac{N}{i} \right \rfloor $$ y el número de puntos en $B$ es claramente $$\lfloor \sqrt{N} \rfloor^2$$

Así que finalmente el número de pares es

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