Comments 28
Какова практическая цель данных исследований?
Здесь явно виден следующий паттерн:
![[m_{i}] \, n_{i} \rightarrow n_{i} + m_{i} \Rightarrow n_{i+1}](https://habrastorage.org/getpro/habr/upload_files/b2f/028/9b3/b2f0289b37c8544ceeed61b902b30381.svg)
Мне не виден, первая же строчка: [1]1 -> 1 + 1 => 2, однако во второй строке n равен 3, а не 2.
В целом, вы рассматриваете какие-то отдельные числа, из ограниченного диапазона, и выводите из них какие-то закономерности, но нигде не доказываете справедливость оных закономерностей для любых чисел. Просто постулируете их. Я не думаю, что это является доказательством чего-либо.
Так ведь рассматриваются нечётные числа. Результаты применения функции одной строки там не связаны со следующей.
Применимость же переходов графа для любых натуральных чисел, по-моему, является очевидной. Это можно более строго расписать, но идея статьи - показать всё в русле конструктивного доказательства через прямые примеры. Вставлять в текст раскадровки для более больших чисел скорее накладно для вёртки и чтения. Возможно, стоит начальные разделы также разбавить кодом.
Как ваше доказательство справится, если правило слегка модифицировать? Например 3n-1 сходится к следующим последовательностям:
2, 1
5, 14, 7, 20, 10
25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136, 68, 34, 17, 50
Не рассматривал этот случай, да и в целом не планировал заход на обобщение этих проблем.
Если навскидку, то вообще не факт что к произвольной kn+a повезёт найти удобно вычислимые переходы между вершинами. В случае 3n-1, думаю, какой-то инсайт может получиться если попробовать заменять числа не на [ (n+1)/2 ] а на [ (n-1)/2 ]. По приведённым циклам что характерно паттерн таки объявляется:
>>>def f(n): return (n - 1) / 2
>>>a = [25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136, 68, 34, 17, 50]
>>>b = [5,14,7,20,10]
>>>c = [2,1]
>>>[f(i) for i in a]
[12.0, 36.5, 18.0, 54.5, 27.0, 81.5, 40.5, 20.0, 60.5, 30.0, 90.5, 45.0, 135.5, 67.5, 33.5, 16.5, 8.0, 24.5]
>>>[f(i) for i in b]
[2.0, 6.5, 3.0, 9.5, 4.5]
>>>[f(i) for i in с]
[0.5, 0.0]
Но чтобы это куда-то доказалось придётся отдельно рассматривать что происходит в структуре которая будет порождаться новыми правилами. Мне кажется, для любой конкретной kn+a проблемы графы могут вести себя очень по-разному и то что для 3n+1 там объявилось бинарное дерево не значит что у схожих формулировок граф тоже окажется бинарным деревом.
Прекрасно, вы изобрели универсальную отмычку к любой математической задаче!
Рецепт: переформулировать условие исходя из тривиальных умозаключений, рассмотреть пару примеров, из этих примеров бездоказательно постулировать универсальные правила, вернуться к исходной задаче для завершения "решения".
Ну вообще-то построенные графовые структуры априори включают в себя множество случаев. Обобщение же ситуации до обратного поиска пути по нечётным и вовсе не может произойти без изучения множества примеров.
Насчёт "бездоказательно постулировать универсальные правила", тут по-моему весь аппарат уже отлично проработан в базовой теории графов из любого курса дискретки. Чтобы утверждать что мы имеем дело с деревом нужно было показать что функции переходов не могут одновременно приводить в одно и тоже число, а также уникальность цикла [1]<->[1.5]. Обе эти ситуации в тексте рассмотрены в 4.2 и 4.4 соответственно.
P.S. пока сидел на толчке придумал следующее расширение гипотезы Коллаца (интересно, не придумал ли я общеизвестное, как всегда?):
Берём любое простое число А >= 3. Берём все простые числа 1 < а[i] < A => множество К.
И вводим следующее два правила преобразования числа х[j]:
1) если x[j] не делится ни на одно число из К, то x[j+1] = A*x[j] +1.
2) иначе находим Кх[j] — произведение всех простых множителей х[j] из К и х[j+1] = х[j]/Kx[j].
Ну и соответсвенно — всегда будет сходится к единице (для трёх чисел, что я успел проверить — действительно так, но там получаются гигансткие разбросы + не факт что есть единственный «околоединичный» цикл ).
Так что практическое применение просвечивается: теория простых чисел, как они меж собой связаны.
В пункте 3 вы рассматриваете два случая: m - четное и m - дробное. Но случай с нечетным m не рассмотрен.
Дальше вы демонстрируете граф и утрвеждаете что в нем есть единственный цикл между 1 и 1.5. Но это недоказанное утверждение. Например, в графе у вас нет чисел 13 и 14 и вы не доказали что все натуральные числа присутствуют в этом графе. Если же допустить, что 13 отсутствует в графе, то это означает что число с порядковым номером 13 образует свой собственный граф (то есть цикл). Таким образом, доказательство нельзя считать строгим.
Спасибо за уточнение по пункту 3, там правка нужна - должно быть не чётное, а "делится надвое с результатом вида [N.5]", т.е что число целое.
Относительно 13 и 14 - они присутствуют в графе как в обычном случае, так и в случае когда это порядковые. Чтобы число отсутствовало в графе у него не должно быть точки входа, однако у всех положительных целых чисел начиная с 1 и соответствующих им порядковым номерам эта точка есть и она единственная.
Чтобы появилось некое число которое не встроено в граф, ему нужно иметь форму отличную от [N] и [N.5], однако построенное от него дерево либо не будет связано с тем что было здесь описано, либо при пересечении породит новую более комплексную структуру. Но во втором случае мы автоматом получим дополнительные переходы которые нужно учитывать и при построении основного графа, и собственно изменит составляющие его числа.
Цикл между 1 и 1.5 единственный для случая двух соседних вершин. Можно расписать таблицу комбинаций входных и выходных переходов на случай собственно двух соседних вершин, но это добавит условных полторы страницы довольно однообразного текста.
А для более длинных циклов уже требуется чтобы был возможен более чем один заход в вершину, чего однако не происходит за счёт невозможности прийти в одну вершину обоими переходами сразу.
А для более длинных циклов уже требуется чтобы был возможен более чем
один заход в вершину, чего однако не происходит за счёт невозможности
прийти в одну вершину обоими переходами сразу.
Почему это требует возможности зайти в вершину двумя путями?
Как вы доказываете несуществование несвязанного графа?
Я имею в виду, что может существовать такое множество чисел P, ни в одно число которого невозможно попасть из вашего графа (начинающегося с единицы). И внутри этого графа P вполне может существовать длинный цикл A -> B -> C -> .... -> A
Пока я не вижу доказательства что продемонстрированный вами граф содержит все полуцелые числа больше или равные единице.
Отличный тейк, пришлось поразмыслить над тотальностью полученного графа.
Что имеем,
Если смотреть на "квадратное отображение", то то во второй строке снизу (1.5, 3.5, ...) мы имеем последовательность нечётных чисел к которым добавлена в общем-то литера ".5". Более верхние строки являются домножением целой части этой строки на степень двойки (например [11.5] -> [22.5] -> [44.5] -> ... ). Т.к первая строка образуется всеми нечётными числами, то последующие строки [N.5] постолбчато состоят из некоторой степени двойки и перемножения простых чисел не равных двойке:
Соответственно, взяв любое [N.5] и мы можем факторизировать из него степени двойки и получить столбец к которому оно относится.
При этом, кстати, число [N.5] в первой строке любого столбца своей целой частью равно оригинальному нечётному числу являющемуся основанием столбца. Так "[3] 5" переходит в "[5.5] 10".
Но таким образом мы однако обосновываем лишь принадлежность всех [N.5] неким столбцам с основаниями [N].
Далее уже надо обосновать что все [N] принадлежат к графу. И тут, пожалуй, происходит получается самое любопытное - из-за того что у нас есть заранее заданная операцией "плюсового перехода" от [N] к [N] влево по диаграмме, то могут возникнуть подозрения что эти переходы в сочетании с переходами от [N.5] к [N] вправо могут породить замкнутый цикл не связанный с исходной вершиной.
Где-то тут, мне кажется, пролегает разделение подходов между дискретными структурами и логическими утверждениями. В случае дерева мы можем спокойно предполагать что оно строится уровень-за-уровнем целиком и в таком случае ситуации с "A -> B -> C -> .... -> A" возникнуть не сможет: каждый шаг будет подразумевать приращение уровня глубины графа с закрытием всех входных путей в новые вершин, а переход на новый уровень при этом возможен лишь с от уровня m к уровню m+1. Соответственно, "A lvl (m) -> B lvl (m+1) -> C lvl (m+2) -> .... -> A lvl (m) " попросту не может случиться.
Если же вместо этого опираться на теоретико-множественный и логистический подход, то пожалуй надо утверждать что выше в этом посте мною обосновано разбиение множества всех валидных [N.5] чисел на классы соответствующие основаниям столбцов, которые можно обозначить например через <[N]>.
И вот тут начинается ад возвращающий нас обратно к стандартной проблеме: относительно <[N]> мы можем сходу утверждать лишь их частичную упорядоченность в случае с цепочками "размена степеней тройки на степени двойки" в [N] (имею в виду движение по типу [9] -> [6] -> [4]).
(минутка философии) Учитывая, что таким образом мы вроде как теряем упорядоченность чисел уже гарантированную нам бинарным деревом, то могу предположить что тут мы либо перескакиваем на иное доказательство того же вопроса, либо из такого перехода следует что построенное дерево само по себе и не отвечало на вопрос о присутствии в нём всех натуральных чисел.
Попробуем теперь всё же атаковать уже эту ситуацию, полагаю что для этого всё в наличии. Но всё-таки,
\отступление
Ради интереса замечу отдельно, что <[N]> для того чтобы не включаться в основной граф должен быть частью цикла вида "<[N]> -> ... -> <[M]> -> <[N]>", при этом для того чтобы цикл замкнулся надо чтобы хотя бы один [N] в нём имел число N делящееся на 3 с остатком 2 чтобы быть столбцом порождающим переходы вправо сверху вниз. И это приведёт нас к ситуации где цикл хотя бы одним своим столбцом порождает бесконечное число дополнительных столбцов. Из который в свою очередь некая часть тоже может порождать новые столбцы, и так далее. Естественно после этого можно начать уже жёсткие фокусы заметив прежде всего что ничто не указывает на уникальность такого цикла, а значит их может быть сколько угодно, потом подготовить ранжирование таких циклов по возможной длине. Итд, итд. Ситуация однозначно жуткая.
Чтобы напрямую побороть эту спекуляцию в таком изложении, мне кажется, может помочь как раз-таки заход на через изучение поведения тут чисел отличных от [N.5] и [N] с дальнейшим сведением ситуации к абсурду через наличие таким образом принципиально разных множеств якобы натуральных чисел. Но для этого, на мой опять же взгляд, к <[N]> должны идти в комплекте операции помогающие соорудить нечто вроде линейных комбинаций.
\конец-отступления
Продолжаю,
Я таки не думал что части статьи статьи после пронумерованных могут быть сколько-то полезные для основного рассуждения, однако теперь мы можем всё же обратиться к дереву нечётных чисел.
Оно опирается на свойства и наполнение основного бинарного дерева, да. Однако за счёт того что там мы задействуем промежуточные вершины, являющиеся побочными для столбцов в основном графе, то в графе нечётных мы имеем уже фиксированные пределы количества дочерних вершин. Благодаря этому тернарное дерево уже может спокойно задавать полную упорядоченность классов <[N]> на множестве нечётных чисел.
И так как в данном случае уже нельзя апеллировать к бесконечному числу порождаемых дочерних <[N]> и переходы в визуальном плане все однонаправленные, то я не представляю каким образом там может получиться цикл.
Дополнительно тут выделю, что функция противохода для нечётных вряд ли возможна без подобной упорядоченности. При этом функция при всей своей лаконичности выдаёт корректные результаты, чего я как-то не встречал ранее. Сама функция тут естественно не является доказательством чего-либо, но я бы отнёс её к сильным аргументам о том что тернарное дерево задаёт упорядоченность <[N]>.
То что тернарное дерево является естественным следствием расположения чисел в бинарном, думаю, дополнительно доказывать не нужно.
По циклам,
Тут ключевой момент, пожалуй, будет в том как именно мы относимся к переходам между вершинами. По всей логике наблюдаемой ситуации переходы задают упорядоченность всем вершинам графа.
Отношение 
на вершинах одного уровня глубины может быть определено по виду перехода ("минусовой", предположим имеет приоритет над "плюсовым") в первых двух вершинах отличающихся в цепочках у 
и 
от общей их цепочки. Сами значения вершин и порядковые номера от них для нас особой роли в общем-то не играют - отношение порядка работает только по количеству собранных цепочками вершин переходов и их вида в точке расхождения цепочек.
В случае цикла из нескольких <[N]> мы получим тут ситуацию вида:
При этом исходя из логики цикла некоторое число таких столбцов всё-таки будут порождать новые <[N]>, что скорее всего приведёт к бесконечному разрастанию данной структуры.
Наличие цикла при этом порождает BSOD у отношения порядка: все новые <[N]> порождённые циклом можно спокойно сравнивать относительно друг друга только до захода в сам цикл.
Если мы немного изучим этот парадокс то вынуждены приходить либо к тому что уже заведомо получилась полная дрянь, либо что все 
равны между собой. Эквивалентность тут естественным образом получается на основании тех же переходов в цепочках вершин.
Таким образом приходится постулировать, что мы имеем дело не с циклом а с некоторой специфичной вершиной из которой имеется множество выходных <[N]> чьё появление не может быть нормально описано неким простым алгоритмом. Т.е это должен быть буквально взрыв самых разных столбцов <[N]> из этой особой вершины, ровно как и просто [N.5] вершин.
Однако прибегая к отношению задающей порядок и зная что из вершины мы имеем по определению алгоритма лишь 1-2 выходных пути, то никакого описанного буйства вершин и <[N]>быть просто не может. Всё их предполагаемое многообразание сведётся отношение эквивалентности к обычному состоянию любого иного столбца - множество [N.5] вычисляемых от основания, и далее во всех возможных вершинах уходы в новые [N] (естественно если получившийся специальный столбец имеет порядковый номер делящийся на три без остатка 2).
Допустим, что на текущий момент всё в порядке,
Продолжаем,
Если теперь смотреть на основание такого столбца как на обычную вершину, то уже бросается в глаза что ей теперь нужна родительская вершина. Тут мы получаем развилку:
1) Родительская вершина оказывается в ином графе с такими же порождающими переходами. В таком случае она соединяется переходом с рассматриваемым столбцом и он становится полноценным поддеревом графа. Какого именно графа? В строгом виде любого у которого в основании стоит вершина к которой нельзя прийти иными способами. В случае основного графа у нас есть такая вершина - это [1]. Более того, показано что из других кандидатов на эту роль тут только [1.5] (это конечно можно в более строгом виде обосновать чем описано в статье).
2) Банальный уход в абсурд, т.к по определению построения цикла все его вершины уже содержали входные переходы.
Оба случая играют на руку утверждению об отсутствии циклов кроме тривиального [1]<->[1.5]. То что этот цикл является уникальным по своим характеристикам и вообще единственным возможным циклом между соседними вершинами, опять же, вытекает из определения операций переходов в обе стороны.
Меня однако весьма смущает, что для построения такого рассуждения о циклах весь описанный в статье подход пожалуй вообще не играет роли. Соответственно, его никто не мешал выдвинуть и ранее, ровно как и оценить\проверить.
Можно также опять воспользоваться полученным тернарным графом:
Резкий переход от основного графа в граф переходов уже между <[N]> для "порождающих вершин" демонстрирует как раз таки создание бесконечного числа новых <[N]> из отдельно взятой. И далее эту бесконечность можно различными аналитическими подходами сужать вплоть до попыток сделать предельный переход с охватом уже всех появляющихся <[N]>.
В общем-то в случае с циклом который сведён до специфичной вершины ситуация с бесконечностью и необходимость разбирать её по слоям б сохранилась. Однако сам первичный список порождённых <[N]> должен быть неупорядоченным. Для произвольного <[N]> у нас такого однако не происходит - все порождаемые нечётные там однозначно заданы алгоритмом, при этом их вполне можно выстроить в порядке появления.
Тернарное дерево доводит это "вполне можно" до готового исполнения, показывая упорядоченность нечётных в оригинальном бинарном графе. В этом случае определять что 
надо также как и в бинарном дереве, только проранжировать дополнительную ветку. Система четырёх переходов в обе стороны переводит произвольное натуральное [N] в другой [N] единственным образом.
Из этого можно заключить что при переходе к нечётным через тернарное дерево мы ликвидировали ситуацию с бесконечными списками. Тут уже нет никакой ячейки которую мог бы занять <[N]> со свойствами исходящих вершин наблюдаемых у свёрнутых до одной вершины циклов.
Поправил пункт 3
Переходы определены для всех
и
начиная с
.
"Входящий" переход соответствует шагу в гипотезе Коллаца (то есть применению операции 3n+1 или n/2 в зависимости от того четное это число или нет). Соответственно у любого числе действительно есть входящее ребро и оно единственное (так как шаг однозначен). Так у числа 8 [3.5] входящее ребро из числа 4 [m=1.5], у числа 15 [7] входящее ребро из числа 46 [22.5]
Исходящий переход, соответственно - числам, которые являются "предками" данного числа. Для любого числа n есть как минимум число 2n, являющееся очевидным "предком". А также может существовать число (n-1)/3, в случае если оно является целым, то есть у нас от 1 до 2 исходящих ребер.
В каждую вершину графа может быть лишь одна точка входа.
Следует из определения входящего ребра - это ребро от предка к потомку, у нас по определению не может быть двух потомков.
В качестве исходной вершины будет положена
, т.к она является наименьшей в графе.
Очевидно.
Граф содержит единственный цикл между двумя соседними вершинами:
![[1] \leftrightarrow [1.5]](https://habrastorage.org/getpro/habr/upload_files/b24/3ac/61b/b243ac61b2a12437b6602149f50e5553.svg)
Требует доказательства, так как вы на этом утверждении основываете все остальное.
При продолжительном движении назад по переходам
переходит в
![[N]](https://habrastorage.org/getpro/habr/upload_files/e74/52f/aad/e7452faadf32c0fbd245650f530adb4d.svg)
Тривиально. Как следуюет из определения входящего ребра, это отношение "предок-потомок", соответствено "обратное движение" по таким ребрам - это "прямое движение" по последовательности чисел. [N.5] является четным числом, соответственно прямое движение будет заключаться в делении на 2, пока мы не получим нечетное [N]
Здесь же стоит отметить, что уникальными являются как значения вершин
графа, так и значения рёбер. Значение вершины однозначно определяет
родительскую вершину а также одну или две дочерние вершины, а значение
ребра - обе вершины которые оно соединяет.
Про вершины понятно - это следует из первого абзаца моего комментария. А вот про значения ребер - требует доказательства.
Насчёт 1 и 1.5 ответил к посту выше.
По значениям рёбер, не посчитал нужным углубляться, т.к далее не используется. Но там всё также упирается в определение переходов между вершинами.
К примеру, в случае [22.5] по изложенному алгоритму мы всё же имеем от него переход вперёд в [15] с разницей +7.5 (здесь плюс для маркировки вида перехода), и переход назад в [11.5] со значением ребра в -11. Т.к мы сохраняем знак, то каждое из чисел мы лишь единожды проверяем на переходах в начале пункта 3, оба из которых легко строятся в обратную сторону. Получаем таким образом, тот же [22.5] через 11*2+0.5 ни одно другое число [11] тут породить просто не сможет.
Вот что было бы интересно доказать отдельно - это наличие в рёбрах графа всех чисел от 0.5 и далее с шагом по 0.5 с обоими знаками, после чего описать альтернативную визуализацию где в вертикальных столбцах получатся останутся уже только числа вида [N] расставленные по значению входящего перехода (связанные с ними рёбра при этом будут иметь крайне хаотичную структуру).
В пункте №2 своего "доказательства" автор заявляет:
Это справедливо также и для чётных чисел
Но это не так. Точнее, автор применил подход, который применим к нечётным числам, к числам чётным. Сам по себе подход применять можно хоть к чему, но только такое применение никак не связывает его с рассматриваемой гипотезой.
В случае с гипотезой имеем предложение автора, предлагающее определить i+1 член последовательности через формулу из двух вариантов:
n[i+1]=1.5*n[i]+0.5
n[i+1]=n[i]/2
Далее автор рассуждает про какие-то конкретные числа, на примере которых он и заключает, что
Это справедливо также и для чётных чисел
Но если бы автор не рассуждал о конкретных числах, а вывел бы простейшую формулу, то всё бы оказалось совсем по другому. Формула такая:
n[i]=2i-1
Из неё, подставляя 2i-1 вместо n[i], получаем:
n[i+1]=3i-1=2i-1+i=n[i]+i
n[i+1]=i-0.5=(2i-1)/2=n[i]/2
То есть для нечётных чисел всё красиво, но вот для чётных, утверждение "Это справедливо также и для чётных чисел" означает, что 3i-1=i-0.5. Немного преобразуем и получим: 2i-0.5=0
После такого очевидного ухода в дебри далее читать данного автора не стоит.
PS
Не смотря на смелое манипулирование математической терминологией автор так и не осилил даже переход к показанной выше очень простой формуле. Поэтому и результат такой.
Про "справедливо также и для чётных чисел" речь шла исключительно о преобразовании чисел в порядковые номера.
Быть может я чего-то совсем уж путаю, но вроде нигде в тексте/коде "нечётная" ветка 
не использована для чётных чисел. Постоянно однако идут указания на разницу поведения в графе числе [N.5] и [N].
Ваша проблема состоит в неумении подать материал. Вам, возможно, какие-то выводы кажутся очевидными, но для остальных это не так. Поэтому перепишите статью полностью. Да, с нуля и не пропуская ни одного доказательства. Кажется слишком тяжёлым трудом? Ну что-ж, оставайтесь с тем, что есть - с игнорированием вас всеми остальными.
По доказательствам подскажу - формулы выше сводят несколько страниц вашего текста к короткому описанию использованных в формулах переменных. То есть на самом деле писать нужно намного меньше, чем написали вы. Только писать нужно по другому. Именно поэтому нужно переписать с нуля.
Вообще, умение строить логические цепочки отличает человека от робота. Вы же выдаёте некий поток уровня GPT-3, но у последнего обычно части текста бессвязны и сразу видно отсутствие логики у писателя, у вас же связи между фрагментами вроде есть, но в целом получается что-то совершенно неудобоваримое. Возможно, так выглядят тексты GPT-4. Не будьте похожим на робота. Сделайте работу по человечески.
Статья получилась сырая, тут уже однозначно согласен, многое хочется переоформить. Во многом это связано с тем, что я ещё банально не чувствую хаброаудиторию, ну да ладно.
В дальнейшем, полагаю, переделанная версия ещё будет, но это явно не пары дней процесс.
----
А насчёт логических-цепочек-и-роботов решительно не соглашусь. У нейронок и компьютеров не с логикой беды, а с семантикой.
Интересно, что существует подмножество чисел, для которого гипотеза доказывается почти так же просто, как для степеней двойки.
Представьте себе число, четверичная запись которого в каждом разряде содержит единицу. Умножьте на три. Прибавьте единицу. Всё!
Такое ощущение, что первые несколько серий этого сериала пропустил, и теперь не совсем понимаю, что происходит.
Очередной заход на Гипотезу Коллатца. Простая арифметика, ориентированные графы и прямая генерация нечётных чисел