Предлагаемая задача не входит в тематический конкурс, но весьма близка к задачам этого конкурса по духу и происхождению. Формулировка задачи (характерная особенность 10-го тура Марафона) не является эталоном математической строгости. Эту строгость легко обеспечить, но мне представляется, что в предлагаемом виде задача выглядит поинтереснее.
Конкурсная задача №94 (4 балла)
Чем замечательна пара чисел 568 и 638?
Докажите, что аналогичных пар бесконечно много (т.е. указаннная пара, вовсе
и не замечательна)
Решение
У чисел 568 и 638 совпадают значения трех основных теоретико-числовых функций. А именно: ф(568) = ф(638), d(568) = d(638) и s(568) = s(638), где ф(n) - функция Эйлера, d(n) - количество, а s(n) - сумма натуральных делитей n. Поскольку все три функции мультипликативны, одновременно умножая 568 и 638 на числа, взаимно простые с каждым из них, получим бесконечно много пар, обладающих аналогичными свойствами.
Обсуждение
Будем называть числа n и m такие, что ф(n) = ф(m), d(n) = d(m), s(n) = s(m),
«похожими» (ничего лучше я не придумал, поскольку термины «близнецы» и
«дружественные числа» уже заняты).
К моему удивлению, я не смог найти никакой информации о похожих числах, хотя
мне представляется маловероятным, что ими никто не интересовался.
Пару похожих чисел назовем «примитивной», если она не получается из другой
пары домножением на одно и то же число (это не означает, что числа в
примитивной паре обязаны быть взаимно просты).
По-видимому, примитивных пар тоже бесконечно много.
Вот несколько первых примитивных пар: (568, 638), (1824, 1836), (3051, 3219),
(4185, 4389), (4960, 5236), (6368, 6764), (7749, 8151).
Пример пары (26355,27962) показывает, что похожие числа могут быть разной
четности.
Похожие числа могут встречаться не только парами, но и тройками. Например, (106120,115938,122322), (227304, 228000,229500).
Мне известны пары не просто похожих, а «очень похожих» чисел. Вот две симпатичные парочки: (54509, 54905); (72703, 72713). Sq(54509) = Sq(54905), а Sq(72703) = Sq(72713), где Sq(n) - количество квадратов по модулю n. Учитывая еще равенство значений функции Мёбиуса и внешенее (по крайней мере, в десятичной записи) сходство чисел в этих парочках, в пору вслед за поэтом воскликнуть «Не те числа назвали близнецами!». Функция Sq(n) также мультипликативна, поэтому пар очень похожих чисел тоже бесконечно много.
Можно рассмотреть и другие усиления «похожести». Например, у похожих чисел 2840 и 3190 совпадают значения Carmichael's lambda function, т.е. наибольшие возможные порядки по модулям 2840 и 3190 равны.
Никому из участников Марафона не удалость узреть все перечисленные свойства, роднящие числа из условия задачи. Андрей Халявин заметил равенство значений функции Эйлера и кратность этого значения разности данных чисел. Виктор Филимоненков обнаружил равенство сумм делителей, а Андрей Извалов - некое следствие этого равенства. Кроме того, были обнаружены некоторые частности, типа «суммы цифр чисел 568 и 638 являют собой пару простых чисел близнецов».
Награды
За решение задачи 94 Андрей Халявин, Виктор Филимоненков и Алексей Извалов получают по 2 призовых балла, а Александр Расстригин - 1 призовой балл.
Эстетическая оценка задачи - 4.5 балла