Задача 3. Нечётная сумма делителей

Чётность суммы — это чётность числа нечётных делителей

Обозначим $\sigma(n)$ сумму делителей. Чётные слагаемые не меняют чётность суммы, а каждое нечётное меняет. Поэтому $\sigma(n)$ нечётна ровно тогда, когда у $n$ нечётное количество нечётных делителей. Например, у $12$ нечётные делители $1, 3$ — их два, и $\sigma(12) = 28$ чётна; у $18$ нечётные делители $1, 3, 9$ — три, и $\sigma(18) = 39$ нечётна.

Какие делители нечётные

Запишем $n = 2^t \cdot m$, где $m$ нечётное ($t \ge 0$). Нечётный делитель $n$ не содержит двойки, поэтому делит $m$; и наоборот, каждый делитель $m$ — нечётный делитель $n$. Значит, нечётные делители $n$ — это ровно все делители $m$.

Когда у m нечётное число делителей

Делители $m$ разбиваются на пары $d$ и $\frac{m}{d}$ (их произведение равно $m$). Делитель остаётся без пары, только если $d = \frac{m}{d}$, то есть $d = \sqrt{m}$. Поэтому делителей у $m$ нечётное число ровно тогда, когда $m$ — точный квадрат: $m = a^2$.

Итак, $\sigma(n)$ нечётна $\iff n = 2^t \cdot a^2$. При чётном $t = 2s$ это квадрат $(2^s a)^2$, при нечётном $t = 2s + 1$ — удвоенный квадрат $2 \cdot (2^s a)^2$. И обратно, у любого квадрата и удвоенного квадрата нечётная часть $m$ — квадрат. Получаем: $\sigma(n)$ нечётна ровно тогда, когда

Считаем на отрезке от 1 до 100

Квадраты: $1, 4, 9, \ldots, 100$ — их $\lfloor \sqrt{100} \rfloor = 10$. Удвоенные квадраты: $2, 8, 18, 32, 50, 72, 98$ — их $\left\lfloor \sqrt{\frac{100}{2}} \right\rfloor = \lfloor \sqrt{50} \rfloor = 7$. Квадрат не может быть удвоенным квадратом (у них разная чётность показателя двойки), поэтому списки не пересекаются: