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

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

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

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

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

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

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

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

Причём, так происходит не всегда. Чтобы старший бит всегда сдвигался на два бита, нужно умножать на четыре. А три — это что-то среднее между 2 и 4. Можно подсчитать, что в среднем сдвиг происходит на чуть больше полтора бита, $\log_2{(3)}=1,5849...$

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

Комментарии (4)


  1. v1000
    29.08.2022 16:07
    +3

    сдвигается в среднем на полбита влево

    это какой-то бит Шрёдингера.


  1. nonickname227
    29.08.2022 17:24
    +2

    А еще можно посмотреть в троичной системе, там 3*x + 1 будет сдвигом влево и дописыванием 1. Тоже красивая картинка получится.


    1. zloddey
      29.08.2022 17:35
      +3

      Значит, надо рассмотреть процесс в трёх измерениях: время, двоичное представление и троичное представление. И уж тогда-то всё будет совсем очевидно!

      (типа, шутка; хз, как там это всё будет выглядеть)


  1. domix32
    30.08.2022 02:15
    +4

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

    Меня больше зантересовали числа которые формируются при помощи операций, про которые писал автор прошлой статьи. Если назвать деление на два down и умножение на 3 up и некоторое произвольное число X, то можно сформировать некоторую математику вокруг полиномов вида ((((X(u|d)u|d)u|d)u|d)u|d)... и вытекает ряд вопрос относительно свойств таких чисел:
    Наткнулся на то что некоторый произвольный полином может иметь несколько целых решений, которые появляются с определенным шагом.
    - все ли произвольные полиномы выдают целые решения или часть из них так и будет рациональным числом?
    - все ли полиномы имеющие целые решения буду генерировать бесконечные последовательности решений или есть полиномы для которых существует единственное целое решение.
    - как произвольный X коррелирует с остальными числами? Взаимно простые, просто простые, непростые и прочие.
    - существует ли общий алгоритм для получения из X некоторого Y посредством применения всех u/d операций
    - сколько вариантов получения некоторого Y сущетвует?
    И многое многое другое. Но я сильно не копался в них, поэтому более формального списка вопросов не писал. Возможно часть из этого покрывается другими вещами.