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

Функция f сопоставляет каждому натуральному числу n сумму остатков от деления n на все натуральные числа, меньшие n.
1) описать все такие n, для которых f(n) = n; (2 балла)
2) Доказать, что для любого натурального k f(2^k) = f(2^k - 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^k. Разобьем натуральные числа, не превосходящие 2^k - 1 на группы, каждая из которых начинается числом 2^t и заканчивается числом 2^t+1 -1 (для t = 0,1,…,k-1).
Количество чисел в t-той группе - 2^t.
Остаток от деления s-1 на первое число t-той группы равен 2^t - 1, а s делится на первое число группы без остатка. Остатки от деления s-1 на каждое из последующих 2^t - 1 чисел t-той группы на 1 меньше остатка от деления s на то же число. Таким образом, в каждой группе суммы остатков для s и s-1 равны. Следовательно, f(s) = f(s-1).

Обсуждение

Некоторые дополнительные сведения о последовательности, описанной в данной задаче, (как и о многих других » марафонских» последовательностях) можно почерпнуть в онлайн-энциклопедии целочисленных последовательностей. Наша последовательность представлена там за номером A004125.

Гипотеза: за исключением случая, описанного во втором пункте ММ36, значения f(n) не повторяются.

Награды

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