Задача 10. Делимость на целую часть квадратного корня

Отрезки с одинаковой целой частью корня

Делитель $[\sqrt{n}]$ меняется не при каждом $n$, а только на точных квадратах. Поэтому удобно собрать вместе числа с одним и тем же $k = [\sqrt{n}]$ — для них делитель одинаковый.

Равенство $[\sqrt{n}] = k$ означает $k \leqslant \sqrt{n} < k + 1$, то есть $k^2 \leqslant n < (k + 1)^2 = k^2 + 2k + 1$. Для целых $n$ это то же самое, что

Так числа $1, 2, 3, \ldots$ делятся на отрезки: $k = 1$ — от $1$ до $3$; $k = 2$ — от $4$ до $8$; $k = 3$ — от $9$ до $15$; … В отрезке $k$ ровно $2k + 1$ чисел.

На каждом отрезке три кратных k

На отрезке $k$ число $n$ подходит, если оно делится на $k$. Кратные $k$ идут через $k$:

Все три лежат на отрезке, а соседние кратные — уже за его краями: $k^2 - k < k^2$ и $k^2 + 3k > k^2 + 2k$. Значит, на каждом отрезке подходят ровно три числа. Например, при $k = 3$ это $9, 12, 15$; при $k = 1$ — все три числа $1, 2, 3$.

Последний отрезок обрезан

Найдём, какие отрезки помещаются в $1, 2, \ldots, 200$. Так как $14^2 = 196 \leqslant 200 < 225 = 15^2$, у чисел до $200$ значения $k$ от $1$ до $14$.

Отрезки $k = 1, \ldots, 13$ кончаются не дальше $13^2 + 2 \cdot 13 = 195 \leqslant 200$ — они целиком внутри и дают $13 \cdot 3 = 39$ чисел.

Отрезок $k = 14$ — это числа от $196$ до $224$, но в нашем списке только $196, \ldots, 200$. Из трёх кратных $196$, $210$, $224$ сюда попадает только $196$.

Ответ

В общем виде: если $K = [\sqrt{N}]$, то ответ равен $3(K - 1)$ плюс количество чисел из $K^2$, $K^2 + K$, $K^2 + 2K$, не превосходящих $N$.