Un número natural [math]n es primo sí y solo sí [math]\sum^n _{i=1}\left \lfloor \frac {n}{i}\right \rfloor=2+\sum^{n-1}_{i=1}\left \lfloor \frac {n-1}{i}\right \rfloor
Demostración
Usaremos el siguiente lema:
Lema: [math]\left\lfloor \frac {n}{k}\right\rfloor-\left\lfloor \frac {n-1}{k}\right\rfloor=1 sí y solo sí [math]k\mid n.
Demostración del lema: Supongamos en un comienzo que [math]k no divide ni a [math]n ni a [math]n-1. Por lo tanto, sus restos en la división por [math]k son consecutivos y sus cocientes iguales. En ese caso, la resta daría 0, y no 1.
Si [math]k divide a [math]n-1, entonces ocurrirá lo mismo.
Sin embargo, si [math]k\mid n, esto equivale a que [math]n=qk y que [math]n-1=(q-1)k+(k-1), por lo que los cocientes son distintos y se llevan en 1. Por lo tanto la condición se cumple (sabiendo que el cociente de una división es la parte entera de la división).
Pasemos ahora a la demostración principal.
La condición del enunciado equivale a que: [math]\left\lfloor \frac {n}{1}\right\rfloor+\left (\sum^{n-1}_{i=2}\left \lfloor \frac {n}{i}\right \rfloor\right)+\left\lfloor \frac {n}{n}\right\rfloor=2+\left\lfloor \frac {n-1}{1}\right\rfloor +\left (\sum^{n-2} _{i=2}\left \lfloor \frac {n-1}{i}\right \rfloor\right )+\left\lfloor \frac {n-1}{n-1}\right\rfloor [math]\sum^{n-1}_{i=2}\left \lfloor \frac {n}{i}\right \rfloor=1+\sum^{n-2} _{i=2}\left \lfloor \frac {n-1}{i}\right \rfloor [math]\left (\sum^{n-2}_{i=2}\left \lfloor \frac {n}{i}\right \rfloor\right)+\left\lfloor \frac {n}{n-1}\right\rfloor=1+\sum^{n-2} _{i=2}\left \lfloor \frac {n-1}{i}\right \rfloor
Como [math]\left\lfloor \frac {n}{n-1}\right\rfloor=1 para [math]n>2, entonces: [math]\sum^{n-2}_{i=2}\left \lfloor \frac {n}{i}\right \rfloor=\sum^{n-2} _{i=2}\left \lfloor \frac {n-1}{i}\right \rfloor
Por lo tanto: [math]\sum^{n-2}_{i=2}\left (\left \lfloor \frac {n}{i}\right \rfloor-\left \lfloor \frac {n-1}{i}\right \rfloor\right )=0
Como todas las restas son positivas, todas deben ser nulas.
Acá se pone en juego el lema de más arriba, por el cual sabemos que como ninguna resta es igual a [math]1, entonces [math]n no debe tener ningún divisor mayor o igual que [math]2 y menor o igual que [math]n-2, y como [math]n-1 no es divisor de [math]n salvo que [math]n=2, entonces [math]n es primo si [math]n>2.
Como [math]n=2 funciona, entonces Todos los primos cumplen.[math]\blacksquare
Aclaración: en la demostración ya asumí que los únicos posibles valores de [math]\left\lfloor \frac {n}{k}\right\rfloor-\left\lfloor \frac {n-1}{k}\right\rfloor son [math]0 y [math]1, lo cual se puede ver del siguiente modo: [math]\left\lfloor \frac {n}{k}\right\rfloor<\frac {n}{k}+1 [math]\left\lfloor \frac {n-1}{k}\right\rfloor\geq \frac {n-1}{k} [math]\left\lfloor \frac {n}{k}\right\rfloor-\left\lfloor \frac {n-1}{k}\right\rfloor<\frac {n}{k}+1- \frac {n-1}{k}=1+\frac {1}{k}
Como [math]\frac {1}{k} no es entero salvo para [math]k=1 (que lo eliminamos en un comienzo), entonces: [math]\left\lfloor \frac {n}{k}\right\rfloor-\left\lfloor \frac {n-1}{k}\right\rfloor\leq 1
[math]\big\lfloor \frac{n}{k} \big\rfloor es la cantidad de múltiplos de [math]k entre [math]1 y [math]n inclusive. O sea, la cantidad de elementos del conjunto [math]M_k = \{k,2k,\dots, k\big\lfloor \frac{n}{k} \big\rfloor\}. Luego [math]\sum_{k = 1}^{n} \big\lfloor \frac{n}{k} \big\rfloor es igual a la cantidad de elementos del multiconjunto [math]T_n = \cup_{k = 1}^{n} \{k,2k,\dots, k\big\lfloor \frac{n}{k} \big\rfloor\}. Sea [math]1 \le m\le n. Contemos cuantas veces aparece [math]m en [math]T_n. Aparece una vez por cada [math]k que divide a [math]m, o sea, tantas veces como divisores tiene. Asi si [math]d(m) es la cantidad de divisores de [math]m, [math]m aparece [math]d(m) veces en [math]T_n. Luego [math]T_n tiene [math]\sum_{m = 1}^{n} d(m) elementos. O sea que [math]\sum_{k = 1}^{n} \big\lfloor \frac{n}{k} \big\rfloor = \sum_{m = 1}^{n} d(m). Ahora el problema se sigue facilmente porque [math]\sum_{k = 1}^{n} \big\lfloor \frac{n}{k} \big\rfloor - \sum_{k = 1}^{n - 1} \big\lfloor \frac{n - 1}{k} \big\rfloor = d(n), y [math]n es primo si y solo si [math]d(n) = 2.
notar que [math]\sum^n_{i=1}\left \lfloor \frac {n}{i}\right \rfloor - \sum^{n-1} _{i=1}\left \lfloor \frac {n-1}{i}\right \rfloor es igual a la cantidad de divisores positivos de n de donde el problema es inmediato.