Конкурсная задача ММ141 (3 балла)

Существуют ли натуральные числа n>1 такие, что σ(σ(n))<1.000000001n? (σ(n) - сумма натуральных делителей числа n.)

Решение

Проще всего найти подходящее число, взяв достаточно большое (больше 10⁹) простое число p так, чтобы p²+p+1 тоже было простым. Тогда в качестве n подойдет p². Наименьшее подходящее p=1000003271. Тогда n=1000006542010699441, σ(σ(n))=1000006543010702714 и σ(σ(n))/n ≈ 1.000000000999997.

Обсуждение

Не обязательно добиваться простоты числа p²+p+1. Достаточно, чтобы оно не имело малых простых делителей. Например, iPhonograph взял n=252097801217². Тогда σ(n)=53840489083·1180399778329 и σ(σ(n))<1.000000001n.

Эта идея - использовать отсутствие малых множителей вместо простоты - позволила Андрею Халявину доказать то, что, по сути, было очевидно и остальным участникам. А именно: для любого M найдутся натуральные n такие, что σ(σ(n))<n(1+1/M).

В самом деле, большинству участников (и ведущему) представляется очевидным, что существует бесконечно много простых p таких, что p²+p+1 тоже просто. Но «представляется очевидным» - не доказательство. Андрей же доказал, что для каждого достаточно большого простого числа p найдется показатель степени k (ну очень большой!) такой, что σ(p^k) не имеет малых делителей. И отсюда получил требуемое утверждение.

Гораздо более интересной, чем ММ141 является такая задача: cуществуют ли натуральные числа n>1 такие, что σ(σ(σ(n)))<1.5n? Но эту задачу мне решить не удалось. Ясно, что необходимым (но недостаточным) условием является существование такого натурального n, что числа n, σ(n), σ(σ(n)) - нечетны. Единственный известный мне нетривиальный пример дает число n=81.

Награды

За правильное решение задачи ММ141 Алексей Волошин, Сергей Половинкин, Николай Дерюгин, Евгений Гужавин, iPhonograph, Sirion и Анатолий Казмерчук получают по 3 призовых балла. За правильное решение более общей задачи Андрей Халявин получает 5 призовых баллов. За верные идеи (не доведенные до конца) Александр Ларин и Кирилл Веденский получают 2 и 1 балл, соответственно.

Эстетическая оценка задачи 4 балла

Разбор задачи ММ141 подготовил Владимир Лецко

---