Поделюсь интересными результатами анализа одной маленькой, но интересной теоремы, гипотезы Коллатца.

Формулировка такая: вам даётся натуральное число. Если оно чётное, вы его делите на два, а если нечётное, умножаете на три и добавляете единицу. И так по кругу. Гипотеза состоит в том, что для натуральных чисел иной судьбы, чем скатиться в цикл 1->4->2->1 нет. То есть, предположение состоит в том, что не появится других циклов — и тем более, таких чисел, которые при такой обработке в среднем всегда только возрастают.

Как бы на это посмотрел бы программист? Прежде всего, целое число для него это набор бит. Количество бит у числа приблизительно подсчитывается логарифмом по основанию 2, с округлением в большую сторону. Семь это три бита «111», восемь это уже четыре бита «1000». Двоичная система счисления — как будто у вас отобрали все цифры с 2 по 9, а числа обозначать надо. Сперва трудно, но привыкнуть можно.

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

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

Умножение на два это сдвиг расстановки в левую сторону, или добавление нолика.

А умножение на три это сложение начальной расстановки и её сдвинутого варианта, x+2x=3x.

При умножении на три происходит следующее: каждый установленный бит пытается установить ещё и более старший бит. А если тот уже установлен, то в результате старший бит наоборот обнуляется и в следующее звено кроме собственного влияния старшего бита на уже его старший бит происходит и перенос разряда, как будто двойной перенос. В общем, ...0011… становится ...1001… Блок из двух значащих цифр расширился до четырёх цифр. Вывод таков: при умножении на три может добавиться два значащих бита.

Причём, так происходит не всегда. Чтобы старший бит всегда сдвигался на два бита, нужно умножать на четыре. А три — это что-то среднее между 2 и 4. Можно подсчитать, что в среднем сдвиг происходит на чуть больше полтора бита,

Небольшой развлекательный анализ умножения на три:
Если биты чередуются по двое, то они остаются чередоваться по двое, только со сдвигом вправо
0100110011001
1110011001011

Края живут своей жизнью.

Если биты чередуются по одному, то результат будет из одних единиц:
01010101
11111111

Только, если из младших бит возникнет перенос, то наоборот, на месте единиц будут нули.

Если есть группа установленных бит, её границы как будто расплываются.
011111111
1011111101

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

Если делить на два на каждом цикле расчёта, то получится группа, у которой старшая стенка сдвигается в среднем на полбита влево, а младшая всегда на бит вправо.

И тут к младшему разряду добавляется единица. Она не просто добавляется, а инициирует лавину переноса, и все единицы, на которые оканчивался блок, становятся нулями. Следующий за ними нолик становится единичкой.

Если не обращать внимание на сдвиги вправо-влево всей расстановки, то гипотеза Коллатца в том и состоит, что какую бы группу бит вы не брали, но при процессе сложения со своим сдвинутым вариантом и последующей лавине переноса с последнего бита, при повторе этого в цикле, всё это схлопнется до одного переключенного в результате такой лавины нолика — одной-единственной единички.

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

Здесь важно отметить, что само место добавления единицы — очень чётко отслеживает младшие биты, и если они лавинно сдвинулись влево, то и сдвиг места добавления не заставит себя ждать.

А теперь слайды.



Группа бит пытается уйти от преследования, но скребок настигает её.

В описанных модифицированных условиях, когда на каждом шаге происходит деление на два, скребок движется со скоростью один бит на цикл, встреча жертвы с преследователем неотвратима. Тем более, ему на встречу с той же скоростью движется правый край группы.

При анализе последствий встречи надо учесть, что хотя борьба скребка с мешаниной и замедляет его проход, но первое: скорость продвижения точно не становится отрицательной. И второе: лавина переключения может преодолевать «скорость света» в один бит на цикл — и поглощать всё пачками.

Ещё, по иллюстрации видно, что надолго скребок останавливается только при встрече с протяжённой группой установленных бит, и группа уменьшается — сдвигая левый край вправо со скоростью света, при этом правый край не расплывается.

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

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

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