Задача 8. Суммы последовательных чисел

Шаг 1. Сумма как произведение

Пусть $n$ есть сумма $k \geq 2$ последовательных натуральных чисел, начиная с $a \geq 1$:

Это арифметическая прогрессия из $k$ членов с крайними членами $a$ и $a+k-1$, поэтому по формуле суммы

Зачем удваивать: дробь неудобна для разговора о делимости, а после удвоения получается произведение двух целых множителей:

Геометрически это «две копии лесенки складываются в прямоугольник $k \times (2a+k-1)$»; на рисунке 1 ниже это показано для $14 = 2+3+4+5$.

Шаг 2. Степени двойки не представимы

Разность множителей $(2a+k-1) - k = 2a-1$ нечётна, поэтому один из множителей чётный, а другой нечётный. Оценим нечётный множитель: если нечётен $k$, то $k \geq 3$ (так как $k \geq 2$); если нечётен $2a+k-1$, то он не меньше $k+1 \geq 3$. В любом случае у числа $2n$ есть нечётный делитель $d \geq 3$; он взаимно прост с $2$, поэтому делит и само $n$.

У степени двойки $2^m$ (включая $1 = 2^0$) единственный нечётный делитель равен $1$. Значит, ни одно из чисел $1, 2, 4, 8, 16, 32$ не является суммой двух или более последовательных натуральных чисел.

Шаг 3. Все остальные числа представимы

Пусть $n$ не степень двойки. Тогда у $n$ есть нечётный делитель $d \geq 3$; запишем $n = d \cdot m$, откуда $2n = d \cdot 2m$. Обозначим через $k$ меньший из множителей $d$ и $2m$, а через $M$ — больший. Почему длиной суммы берём именно меньший: в равенстве $2n = k\,(2a+k-1)$ второй множитель больше первого, так как $2a+k-1 \geq k+1$ при $a \geq 1$. Поскольку $d$ нечётно, а $2m$ чётно, эти множители различны, поэтому $M - k$ нечётна и положительна.

Положим $a = \dfrac{M-k+1}{2}$; это целое число, не меньшее $1$. Тогда $2a + k - 1 = M$ и

то есть $n$ есть сумма $k$ последовательных чисел от $a$. Осталось проверить $k \geq 2$: оба множителя не меньше $2$, так как $d \geq 3$ и $2m \geq 2$.

Примеры из нашего диапазона:

• $n = 20 = 5 \cdot 4$: множители $5$ и $8$, значит $k = 5$, $a = 2$, и $2+3+4+5+6 = 20$;
• $n = 6 = 3 \cdot 2$: множители $3$ и $4$, значит $k = 3$, $a = 1$, и $1+2+3 = 6$;
• $n = 48 = 3 \cdot 16$: множители $3$ и $32$, значит $k = 3$, $a = 15$, и $15+16+17 = 48$.

Шаг 4. Подсчёт для чисел от 1 до 50

Итак, число представимо тогда и только тогда, когда оно не является степенью двойки. Среди чисел $1, 2, \dots, 50$ степеней двойки шесть:

Важно не забыть $1 = 2^0$: сумма двух или более натуральных чисел не меньше $1 + 2 = 3$, так что $1$ и $2$ действительно не представимы. Следующая степень двойки, $64$, уже больше $50$.

Ответ: $50 - 6 = 44$ числа (рисунок 2).