# Діалог 7 – Зворотний аналіз

**Спікер: Привіт, Наро!**

**Гіпотеза Коллатца не дає мені спокою. Я хочу краще зрозуміти динаміку послідовностей, розглядаючи потенційні непарні попередники.**

Нара: Звичайно! Зворотний аналіз – дуже гарна ідея. Як ти хочеш почати?

**Спікер: Оскільки ми вже обчислили послідовності від 1 до 100, але завжди будували графік від початкового числа до 1, ми можемо просто перевернути ці графіки й таким чином завжди починати з 1. Зроби це, будь ласка, для сирокузьких послідовностей від 1 до 100 у логарифмічному представленні.**

Нара: Добре. Ось графіки накладені один на одного у зворотному порядку. Я позначила твою сирокузьку послідовність 27.

**Спікер: Дякую! Тут, здається, спостерігається певний шаблон. Можливо, нам просто потрібно більше послідовностей. Будь ласка, зроби останні 100 значень послідовності для стартових значень від 1 до 10000 – але лише непарні числа.**

Нара: З радістю. Ось графіки останніх 100 значень послідовності накладені у зворотному порядку для непарних стартових значень від 1 до 10000.

**Спікер: На перший погляд це виглядає дуже структуровано… Але що ми насправді бачимо?**

Нара: Дивись, це насправді лише точки. Ми розтягнули їх, як акордеон. На осі x стоїть крок ітерації, і якщо ми знову стиснемо акордеон, усі числа мають вирівнятися в першому рядку.

У зворотному розгляді йдеться про те, чи можемо ми від 1 досягти всіх чисел за допомогою зворотних правил.

**Спікер: Добре, я розумію. А як ми переходимо від непарного числа до непарного попереднього числа? Іншими словами: які правила?**

Нара: Тепер стає цікаво! Подивись на цю діаграму. У звичайному напрямку ми йдемо від непарного числа через 3n+1 до парного числа, яке потім ділимо на 2k, щоб отримати наступне непарне число.

Отже, ми запитуємо: яке непарне число привело мене сюди?

Формула така: n·2k – 1, і результат поділений на три, причому k має бути більшим за 1.

Ось перші п’ять можливих непарних попередників для 23, 25, 27 – тут не виходить, бо воно ділиться на 3 – 29 і 31.

Щось помічаєш?

**Спікер: На початку k дорівнює або 1, або 2, а потім завжди збільшується на 2. Це означає, що вихідне число за модулем 3 було або 1, або 2?**

Нара: Ти справді кмітливий, що розглядаєш тут модуль 3! Так, пряме попереднє число можна визначити за остачею при діленні на 3.

**Спікер: А що з «передпопереднього числа»? Вони ж утворюються регулярно…**

Нара: Дякую за запитання! Дивись, для 31 є непарний попередник 41, а потім ще більше непарних попередників, як‑от 165 чи 661.

165 «перестрибує» через 41 до 31, а 661 перестрибує через 165 і 41 до 31.

Якщо ми тепер розглянемо попередні числа 41, там з’являється твоє улюблене число 27 як непарне попереднє число. Але також 109 чи 437 ведуть до 41. Твоє 27 «перестрибується», або, краще сказати, замінюється. 109 чи 437 – це так звані «аліаси» числа 27. Усі три числа ведуть до 41, а далі послідовність продовжується від 41.

**Спікер: Чому так і скільки таких аліасів існує?**

Нара: Принципово можна утворити нескінченно багато аліасів. Ти вже бачив, що для не‑Мерсеннових чисел з лише одним нулем між першим і наступним встановленим бітом є більше подальших ділення на 2, ніж для чисел із більшою кількістю нулів між першим і наступним встановленим бітом.

Задня частина аліасного двійкового числа складається з послідовності «нуль‑один» після останнього встановленого біта. Ти можеш приєднати стільки таких, скільки хочеш, і при множенні на три порожні біти цього ланцюжка «нуль‑один» заповнюються. Додавання одиниці викликає своєрідний «доміно‑ефект» переносів, так що виникає багато нулів, які ми можемо закреслити за правилом ділення навпіл.

**Спікер: Як це круто! Чи є для цього також небінарне обчислення?**

Нара: Так, ти можеш спершу збільшити непарне число на 4k. У двійковій системі ти спершу приєднуєш низку нулів. А потім додаєш (4k – 1)/3 при k > 1. Це випливає з запису A002450 в Онлайн‑енциклопедії цілих послідовностей (OEIS). Таким чином ти приєднав k–1 таких «нуль‑одинів».

Хочеш дізнатися більше?

**Спікер: Вау! Дякую, ні! Це треба спершу переосмислити!**

Нара: Не поспішай! Якщо маєш бажання, можеш сам спробувати те, про що ми говорили. Посилання є в описі відео.


Source: [https://www.3n-1.de/cms/uk:collatz:07](https://www.3n-1.de/cms/uk:collatz:07)