Круто! А почему так?

На одном из математических пабликов появилось короткое видео с «математической магией». Там выбиралось произвольное число, кратное трём, каждая из его цифр возводилась в куб и в сумме получалось новое число. Когда эту операцию повторяли ещё несколько раз, получалось число 153. Для другого числа, делящегося на 3 эта процедура вновь сходилась к числу 153. И вообще, похоже что независимо от начально выбранного числа, если оно делится на 3, последовательное вычисление суммы кубов цифр приводит к этому же результату. Волшебство!

Я решил, что это неплохой повод поговорить о динамических системах, их аттракторах и немного о графах.

Изучение динамических систем внешне может выглядеть, как баловство с калькулятором. Набираешь произвольное число и применяешь к нему много раз один и тот же набор арифметических операций, глядя на то, что с ним происходит. Чаще всего, ничего особо интересного — оно либо растёт, выходя за пределы возможностей калькулятора (например, если всё время умножать на 2), либо уменьшается до нуля (например, если всё время делить на два). Иногда, правда, бывает что-то интереснее. Если много раз вычислять косинус от какого угодно числа, то результат будет сходиться к 0,7391…, а если квадратный корень, то числа будут сходиться к единице. В этом несложно убедиться и это несложно объяснить.

А что вообще может происходить при многократном применении какой-то формулы, переводящей натуральные числа в натуральные? Вариантов всего три: 1) бесконечный рост результатов, 2) одно или несколько чисел, к которым эти результаты сходятся (неподвижные точки), и 3) бесконечно повторяющиеся циклические последовательности (циклы). Варианты 2) и 3) называются аттракторами системы, они притягивают к себе результаты вычислений.

В вещественных числах есть ещё один вариант — странный аттрактор. Это хаотичная последовательность, никогда не зацикливающаяся. Но в целых числах такой красоты не бывает. Смотрите сами, если последовательность не увеличиваются неограниченно, то все её члены оказываются меньше какого-то числа R. Но на отрезке от 1 до R есть лишь конечное число целых чисел, и поскольку следующий шаг целиком зависит от предыдущего, бегать по этому отрезку, ни разу не повторившись, не получится. В течение R шагов, последовательность неизбежно попадёт на число, в котором она уже побывала и зациклится.

Так что сходимость к числу 153 последовательности, вычисляемой с помощью функции

f : n ⟶ сумма кубов цифр n,

не так уж удивительна. Число 153 примечательно тем, что сумма кубов его цифр равна 1³ + 5³ + 3³ = 153. Так что это, действительно неподвижная точка нашей динамической системы. Но у математика могут возникнуть другие вопросы: А есть ли числа, не делящиеся на 3, но не притягивающиеся к числу 153? А есть ли другие аттракторы: неподвижные точки или циклы?

Так что тут есть есть место для исследования.

Начнём с глобального вопроса: может ли последовательность, генерируемая функцией f расти неограниченно? И сразу готовы ответить: нет, не может. Добавление слева к числу ещё одной цифры, увеличивает его на порядок, а сумму кубов его цифр — не более чем на 729 = 9³. Геометрическая прогрессия неизбежно обгонит арифметическую, а это значит, что большие числа будут под действием функции f уменьшаться. Это позволяет понять, что за пределами некоего радиуса, под действием функции f вся числовая ось будет только сжиматься.

Этот радиус можно вычислить. Рассмотрим поведение тех чисел, которые по действием функции f растут быстрее всего. Это числа, состоящие из одних девяток:

9 → 729

99 → 1458

999 → 2187

9999 → 2916

Получается, что все трёхзначные числа отображаются на отрезок [1, 2187], а среди четырёхзначных большая часть становится меньше и переходят на отрезок [1, 2916]. Рассмотрим число 1999. Оно входит в отрезок [1, 2187], но отображается в число 2188, выходящее за его пределы. Все остальные четырёхзначные числа будут отображаться в числа не превышающие 2188. Это и есть критическое число, которым ограничена область немонотонного поведения нашего отображения. Значит, наша система может иметь только аттракторы и циклы.

Следующий шаг в анализе — отыскать все эти аттракторы. Для этого мы воспользуемся элементами теории графов.

Действие функции y = f(x) можно представить как стрелку, соединяющую два числа: x ⟶ y. Если мы построим такие стрелки для всех чисел от 1 до 2188, то получим большую сетку, которая называется ориентированным графом. Существуют очень эффективные способы построения таких графов и их анализа. В частности, простым алгоритмом, можно выявить все циклы в графе, если они есть. Конечно, 2188 чисел, это уже многовато для ручных вычислений, так что я воспользовался компьютером. Программка в шесть строк вычислила всё необходимое и показала, что наш граф имеет девять аттракторов: пять точек 1, 153, 370, 371, 407; и четыре цикла: 55→250→133, 136→244, 160→217→352, 919→1459. Оказалось, что эта система имеет достаточно богатую динамическую структуру.

Осталось показать, что 153 это единственный аттрактор для чисел, кратных 3. Как известно, сумму кубов можно разложить на произведение, причём, один из множителей будет равен сумме самих чисел:

a³ + b³ + c³ + … = (a + b + c + …)(…).

Если число делится на 3, то сумма его цифр тоже делится на три, а это значит, что и сумма кубов цифр этого числа обязана делиться на 3. Отсюда делаем важный вывод: функция f отображает множество чисел, кратных трём, само на себя. Получается, у нашей системы есть замкнутая подсистема! Быстрый взгляд на найденные нами аттракторы показывает, что среди неподвижных точек и циклов число 153 единственное, кратное трём. Следовательно, найденная нами подсистема имеет единственный аттрактор — неподвижную точку 153.

Весь граф нашей системы распадается на девять подграфов, не связанных друг с другом. Выглядят они довольно забавно и похожи на харовые водоросли. Наш подграф, содержащий числа, кратные трём, — красненький посередине.

Подграфы для девяти аттракторов на которые распадается отрезок [1, 2188]. Все числа за пределами этого отрезка присоединяются к тому или иному подграфу.

Забавные пучки веток на графе получаются оттого, что к если число вида abc функция f приводит к какому-то узлу, то к нему же приводятся как минимум ещё пять чисел вида acb, bac, bca, cab и cba. Если цифр в исходном числе четыре, то вместе с ним появится пучок, максимум из 23 веток, впрочем, если цифры повторяются, то "родственных" веток будет меньше.

Несколько увлёкшись, я выяснил, что если заменить в нашем преобразовании кубы на квадраты, то аттракторов будет всего два — число 1 и цикл 4←20←42←145←89←58←37←16. А при использовании четвёртых степеней, аттракторов будет шесть: кроме четырёх неподвижных точек, два цикла длины 2 и 7. И, наконец, для пятой степени аттракторов уже 16, среди которых есть цикл длиной в 28 шагов. Поскольку x⁵+y⁵+... = (x+y+...)(...), числа, кратные трём опять образуют замкнутую подсистему, однако на этот раз вона имеет пять аттракторов: четыре неподвижные точки и цикл в 22 шага.

Конечно же, эта задачка не представляет большой практической важности. Но мне было интересно выяснить как далеко мне удастся продвинуться в её анализе, не прибегая к сложным методам. Оказалось, что до конца.

Целочисленные динамические системы не такие интригующие, как вещественнозначные, но и среди них есть знаменитости. Про одну из них слышали все любители математики — это система Коллатца, известная под именем «3n+1». Один её аттрактор, цикл, хорошо известен. Но единственный он или нет, неизвестно. Тысячи математиков во всём мире пытаются найти метод, который может дать ответ. Именно метод, а не результат имеет смысл в таких задачах.