\( \left\lceil \dfrac x2 \right\rceil + x + xy \)

Очередное задание взято из списка задач The Harvard-MIT Mathematics Tournament (ноябрь 2015 года).

86. (Calvin Deng) Вычислите сумму натуральных \( n \leqslant 2015 \) таких, которые могут быть представлены в виде \[
n = \left\lceil \dfrac k2 \right\rceil + m + km
\ \mbox { где } k \mbox, \, m \in \mathbb N .
\tag {86.1}
\]

Обозначение \( \left\lceil x \right\rceil \) задает наименьшее целое число, большее или равное \( x \). За функцией \(
f (x) = \left\lceil x \right\rceil \) закрепилось название потолок.

Решение. Ответим на вопрос, какие из целых чисел от \( 1 \) до \( 2015 \) не могут быть представлены в виде (86.1).

1) Пусть \( k \) — нечетное число, т.е. \( k = 2a -1 \), где \(
a \in \mathbb N \). Тогда
\[
n = a + m + m (2a - 1) = a + 2ma = a (2m + 1) .
\] Поскольку \( a \) и \( m \) пробегают натуральный ряд, то
\[
a (2m + 1) \not= 2^b \mbox,
\ \mbox { где }
b \in \mathbb Z_{\geqslant 0} .
\] Таким образом, при нечетных \( k \) число \( n \) не принимает лишь значения, равные неотрицательной целой степени \( 2 \)-ки \(
(1, \, 2, \, 4, \, \ldots) \).

2) Рассмотрим случай, \( k \) — четное число, т.е. \( k = 2a \), где \(
a \in \mathbb N \). Тогда
\[
n = a + m + 2am ,
\ \mbox { или}
\] \[
2n+1 = (2a + 1) (2m + 1) .
\] Пусть \(
n = 2^b
\), где \( b \in \mathbb Z_{\geqslant 0} \). Получим
\[
2^{b+1} + 1 = (2a + 1) (2m + 1) .
\tag {86.2}
\] Правая часть (86.2) принимает значения, которые равны любому нечетному составному числу. В левой части (86.2) стоят простые числа только при \(
b = 0, \, 1, \, 3, \, 7, \, 15 \), поскольку \(
2^{b+1} + 1\) — простые числа Ферма. Значит, при указанных значениях \( b \) (и только при этих значениях) равенство (86.2) не выполняется.

Делаем вывод, что \[
n \in \mathbb N_{\leqslant 2015} \setminus \{ 1, \, 2, \, 8, \, 128 \} .
\]
Ответ: \(
\dfrac {2015 \cdot 2016} 2 - ( 1 + 2 + 8 + 128 ) =
2030981
\).