=====ММ36=====

**Конкурсная задача ММ36** (5 баллов)

Функция f сопоставляет каждому натуральному числу n сумму остатков от деления n на все натуральные числа, меньшие n.\\
1) описать все такие n, для которых f(n) = n; (2 балла)\\
2) Доказать, что для любого натурального k f(2<sup>k</sup>) = f(2<sup>k</sup> - 1). (3 балла)\\

**Решение**

1) Ясно, что если k превышает половину n, то n mod k = n - k.\\
Поэтому за исключением нескольких начальных значений n\\
f(n) > 1 + 2 + ... + [(n-1)/2] ([x] означает целую часть числа x).\\
При n больших 10 эта сумма, а значит и f(n), больше n.\\
Подсчитывая f(n) для n, не превосходящих 10, находим, что единственным числом, для которого f(n) = n, является 8.

2) Обозначим s =2<sup>k</sup>. Разобьем натуральные числа, не превосходящие 2<sup>k</sup> - 1 на группы, каждая из которых начинается числом 2<sup>t</sup> и заканчивается числом 2<sup>t</sup>+1 -1 (для t = 0,1,...,k-1).\\
Количество чисел в t-той группе - 2<sup>t</sup>.\\
Остаток от деления s-1 на первое число t-той группы равен 2<sup>t</sup> - 1,
а s делится на первое число группы без остатка. Остатки от деления s-1 на каждое из последующих 2<sup>t</sup> - 1 чисел t-той группы на 1 меньше остатка от деления s на то же число.
Таким образом, в каждой группе суммы остатков для s и s-1 равны. Следовательно, f(s) = f(s-1).

**Обсуждение**

Некоторые дополнительные сведения о последовательности, описанной в данной задаче, (как и о многих других " марафонских" последовательностях) можно почерпнуть в онлайн-энциклопедии целочисленных последовательностей. Наша последовательность представлена там за номером [[http://oeis.org/A004125 | A004125]].

Гипотеза, что за исключением случая, описанного во втором пункте ММ36, значения f(n) не повторяются, не подтвердилась.
Вот несколько контрпримеров, найденных Юрием Макарычевым:\\
m = 38183, n = 38185: f(m) = f(n) = 258840858\\
m = 458009, n = 458011: f(m) = f(n) = 37241677057\\
m = 776111, n = 776113: f(m) = f(n) = 106936975149\\
m = 65676407, n= 65676409: f(m) = f(n) = 765769022511763.

**Награды**

За правильное решение этой задачи Влад Франк, Мигель Митрофанов и Иван Козначеев получают по 5 призовых баллов. Антон Филиппов получает 2 призовых балла за правильное решение первого пункта. 
----