Comments 28
Сильна Россия математиками :) Не всё ещё потеряно
Пока не дочитал но нашел как будто ошибку. Сумма ряда степеней тройки должна была дать 
а у вас ошибочно сведена к 
. Проверьте, пожалуйста.
Вы правы в том, что здесь есть ошибка, и правы в своих рассуждениях. НО ошибка не в том. Я обозначения чуть сдвинул при переносе на хабр (ошибочно). Там первый член не 3^n, а 3^(n-1), тогда все будет правильно. Замечу, что этой ошибки нет в дальнейших рассуждениях. (она появилась при переносе с word в хабр).
Автор молодец - сузил одно бесконечное множество до другого бесконечного множества той же мощности
Как насчет троичной системы? Тогда можно представить умножение на три как сдвиг влево. (/шутка)
Неоднократно уже было сказано, что для гипотезы Коллатца достаточно рассмотреть все нечетные числа.
Где про это прочитать? Ну что из гипотезы Коллатца можно выкинуть чётные числа?
Ну это как бы очевидно. Любое четное число - это какое-то нечетное число, домноженное на какую-то степень двойки, и тупо применяя алгоритм из гипотезы мы за некоторое количество шагов деления на 2 дойдем до этого самого нечетного числа. Доказательство или опровержение гипотезы для всех нечетных чисел автоматически распространяется и на все четные числа.
Если число чётное, мы будем делить его последовательно на 2, пока оно не станет нечётным.
Спасибо за статью. В тексте упоминается небезызвестный проект «Collatz Conjecture». Я вот, честно говоря, с наскоку на Хабре про него отдельной статьи не нашёл. Может быть кто-то в курсе и поделится ссылкой. А если таковой нет, то, кажется, это большое упущение. Очень интересно знать, как он работает как там все оптимизировано (простор для оптимизаций, кажется, большой). Не исключено, что развитие рассуждений, приведённых в статье, может помочь ускорить процесс поиска циклов.
Интересный способ у вас считать единицы. Сначала в строку превращать, а потом строки же сравнивать. Чем вам целочисленная математика не угодила?
А вообще попытки решать в бинарном представлении уже делались, только числа в итоге представлялись как диадические. В том же представлении были и утверждения, которые требовали доказательства для того чтобы считать гипотезу Коллатца верной.
На самом деле не обязательно считать до 1. Достаточно доказать, что в какой-то момент последовательность выдаст число меньше изначального. А далее по индукции.
Число шагов до этого момента в зависимости от начального числа выглядит как-то так:
В диапазоне до 1e9 самый высокий пик у числа 217740015, которому требуется 644 шага, чтобы опуститься ниже. По мере увеличения диапазона пики растут, но скорость роста стремительно замедляется. Так, для диапазона до 1e8 самый высокий пик у числа 63728127 со значением в 613.
Круто! (но неправильно)
63728127 → 949 шагов, а не 613
217740015 → 793 шага, а не 644
https://en.wikipedia.org/wiki/Collatz_conjecture#Empirical_data
less than 10 is 9, which has 19 steps,
less than 100 is 97, which has 118 steps,
less than 1000 is 871, which has 178 steps,
less than 10^4 is 6171, which has 261 steps,
less than 10^5 is 77031, which has 350 steps,
less than 10^6 is 837799, which has 524 steps,
less than 10^7 is 8400511, which has 685 steps,
less than 10^8 is 63728127, which has 949 steps,
less than 10^9 is 670617279, which has 986 steps,
less than 10^10 is 9780657630, which has 1132 steps,
less than 10^11 is 75128138247, which has 1228 steps,
less than 10^12 is 989345275647, which has 1348 steps.
Нужно посмотреть как оно выглядит в троичной системе, кстати
Вот и не верь после этого в коллективное бессознательное, неделю назад ехал с дачи и раскидывал в уме последовательности гипотезы в двоичной с.с. и тоже наткнулся на простоту. Мне показалось элегантной интерпретация 3n+1 как 4n-(n-1), т.к. умножение на 4 это добавление двух 0. А вычитание проще чем утроение… По ощущениям)
Читая комментарии ниже тоже хотел бы отметить, что фундаментально нужно изучить поведение ф-ии 4n-(n-1) для последовательностей из 4-6 символов во всех возможных вариантах - там максимум 2^12 вариантов. Если я верно помню свою логику, то гипотеза может считаться доказанной, если поведение ф-ии не будет приводить к появлению беспрерывного ряда единиц с 0 на конце.
Напишу один маленький вывод который может и очевиден, но кажется интересным
Через n шагов, где n - длина двоичного представления исходного числа, в последовательности больше не встречается подряд идущих 0, 1 или их чередований длинной более 12, не зависимо от того какое взято исходное число
Возможно такой вывод, если рассматривать задачу как исполнение клеточного автомата, можно подвести к тому что последовательности приходят к какому то ограниченному подмножеству, которое уже обязательно доходит до 1
Не могли бы вы объяснить данный вывод. Я не понял из чего он получился.
можно поизучать эволюцию таких кусочков последовательносии (именно в версии с переформулировкой про прибавление 2^k)
эволюция кусочка за 1 шаг зависит только от того что справа от него и от него самого. можно просто применять изолированно к нему правила 3x+0, 3x+1, 3x+2 и изучить как зависит необходимость прибавления именно 0, 1 или 2 от того что справа от кусочка (перенести из младших разрядов справа может только 0, 1 и 2)
там довольно быстро получается (а может это и ошибочно) что кусочки из 12 и более единиц получаеются на следующем шаге только после кусочка из бОльшего числа единиц
к полному формальному доказательству там надо еще дойти, аккуратно проверив что нет исключений. я проверяя этот факт вроде пришел к уверенности что все честно получается, но полной цепочки рассуждений не сохранилось
визуально некие принциаы можно заметить если погенерировать числа и применять к ним правила.
там видно что участков из единиц левая граница не меняется, а правая "испаряется"
у нулей примерно то же самое только наоборот справа появляются единицы
это наталкивает на мысль что можно изучать отдельные куски последовательности
пс - уточнение по последовательностям из нулей. тут не идут в расчет те нули что на каждом из шагов появляются с правого края.
псс - изучая мне было удобнее вообще перевернуть двоичный представления, чтобы меньше отвлекаться на то что это число, а не что то больше похожее на клеточный автомат. + эволюция начинает идти не слева направо, а справа налево, а это проще воспринимать
Понял, спасибо за объяснение.
вы если придете к такому же выводу или наоборот к опровержению, напишите сюда?
поделюсь ссылкой на схожую с вашей идею переформулировки https://www.researchgate.net/publication/369976753_Reformulating_Collatz_Conjecture_Without_Numerical_Concepts
Я не математик. Я занимался этим чтобы отвлечься от основной деятельности, отдохнуть. Вообще не планировал больше рассматривать эту задачу, т.к. не считаю себя достаточно компетентным, чтобы продвинуться ещё как-то в этом направлении. Но если, вдруг, опять что-то буду с ней делать, то обязательно напишу ещё одну статью)
Гипотеза Коллатца. Взгляд со стороны двоичной системы счислений