Равные суммы остатков

[Ktina]

Разделим натуральное число n на числа 1, 2, 3, ... , n и обозначим сумму получившихся остатков за S(n).
Доказать, что для бесконечно многих n выполняется $S(n)=S(n+1)$.

[nnosipov]

Старенькая задачка. Было бы интересно узнать, когда и где она впервые появилась.

[Ktina]

nnosipov в сообщении #514395 писал(а):

Старенькая задачка. Было бы интересно узнать, когда и где она впервые появилась.

Венгерская олимпиада, 1981.

(Оффтоп)

(кстати, год рождения Маргоши)

[nnosipov]

Ktina в сообщении #514400 писал(а):

Венгерская олимпиада, 1981.

Спасибо.

(Оффтоп)

А кто такая Маргоша? Ксюшу знаю, о Катеньке наслышан, а вот про Маргошу впервые слышу ...

[Dave]

Эту задачу раньше не встречал. Нужно брать $n=2^m-1$, насколько я понимаю

[Ktina]

Dave в сообщении #514405 писал(а):

Эту задачу раньше не встречал. Нужно брать $n=2^m-1$, насколько я понимаю

Насчёт "нужно" - не уверена. Это уже другая задача - доказать (или опровергнуть), что только такие пары чисел имеют равные суммы остатков.
Но вот то, что "можно" - это точно!

[Dave]

Ktina в сообщении #514410 писал(а):

Насчёт "нужно" - не уверена.

Согласен. Я имел ввиду не столько в смысле математической необходимости, сколько в ракурсе совпадения с общеизвестным решением, раз утверждают, что задача старая.

[Руст]

Точнее $S(n+1)+\sigma(n+1)=S(n)+n$, где $\sigma(n+1)$ - сумма делителей числа $n+1$ за исключением самого числа $n+1$. Отсюда $\sigma(n+1)=n$. Ясно, что $n+1=2^m$ решение. Однако могут быть и другие решения.

[maxal]

Руст в сообщении #514414 писал(а):

Ясно, что $n+1=2^m$ решение. Однако могут быть и другие решения.

Существование других решений эквивалентно существованию почти совершенных чисел отличных от степеней 2-ки (статья в википедии), а это - открытая проблема.

Кстати, $S(n)$ представлена в OEIS последовательностью A004125 - там есть много полезной информации.