Разделы: Математика
Размещена 28.10.2024. Последняя правка: 07.11.2024.
Просмотров - 608

Построение ориентированного графа Коллатца (гипотеза Коллатца)

Усов Геннадий Григорьевич

к.т.н.

МГУ, 1972

пенсионер

УДК 511

Введение

Среди нерешённых математических задач, которые математиками рассматриваются постоянно, есть гипотеза Коллатца[1].

Немецкий математик Лотар Коллатц сформулировал в 1934 году следующую задачу [2]:

выбирается любое натуральное число n, с которым делаются следующие операции:

- если n - чётное число, то число n делится на число 2.

- если n - нечётное число, то число n умножается на число 3 и добавляется число 1.

Над полученным числом выполняются те же самые действия и так далее. В результате получается некоторая последовательность чисел, которая называется последовательностью Коллатца.

Формулировка гипотезы Коллатца [2]: какие бы начальные числа n не выбирались, рано и поздно после применения операций числом последовательности будет число 1.

С другой стороны, если существует некоторое начальное натуральное число последовательности Коллатца,  в которой отсутствует число 1, то это означает, что гипотеза Коллатца неверна.

При исследовании последовательности Коллатца удобнее рассматривать только нечётные числа. Ведь при умножении нечётного числа последовательности на число 3 с прибавлением 1 получается чётное число. Поэтому, числа последовательности Коллатца V можно представить следующими формулами:

- если:  V_i mod(2) = 1,  то V_i+1 = (V_i * 3 + 1) / 2,                                                                     (1)

- если:  V_i mod(2) = 0,  то V_i+1 = V_i / 2.

В настоящее время отсутствует строгое доказательство того, что гипотеза Коллатца верна для всех натуральных чисел.

При этом, были проверены все натуральные числа, меньшие 9 789 690 303 392 599 179 036, и каждое из них за конечное количество шагов соответствовало условиям гипотезы Коллатца[2].

 

Актуальность.

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

 

Цели и задачи

В работе [2] показан граф Коллатца для первых уровней в количестве 21. Граф Коллатца строится на числе 1 и представляет собой действие, обратное действию гипотезы Коллатца.

Теперь необходимо упорядочить этот граф, а именно, ввести такие понятия, как стволы, так и ветки. И уже на этих элементах графа «поместить» конкретные числа.

Такой граф будет называться ориентированным графом Коллатца.

При этом у ориентированного графа должны быть основной ствол, ветки и боковые стволы, или просто стволы. Каждый из боковых стволов строится на одной из веток.

 

Задача 1. Построение основного ствола ориентированного графа.

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

Допустим в последовательности Коллатца V имеется n чисел.

Поскольку конечное число этой последовательности V_n есть число 1, то:

     V_n-1 = 2^k,                                                                                                                               (2)

где k – натуральное число.

Следовательно, основной ствол графа будет состоять из чисел 2^k.

Если рассмотреть обратное построение чисел последовательности Коллатца, то согласно (1) получаем:

      V_n-2 = ( V_n-1 * 2^k – 1 ) / 3.                                                                                                      (3)

Тогда числами основного ствола графа будут числа, для которых выполняется условие (3).

Поэтому числами основного ствола графа будут числа 1, 4, 16, 63, 256, 1024, и т.д.

Аналогично, для любого ствола графа будет указываться нечётное число, к которому «крепится» данный ствол.

В частности, основной ствол графа «крепится» на числе 1.

 

Задача 2. Построение веток графа, отходящих от ствола.

Каждая ветка графа должна опираться на числа либо на основном стволе графа, либо на боковом стволе графа.

Построение ветки от ствола заключается в поиске нечётных чисел V_i+1  таких, что выполняется условие следующего уравнения:

      V_i+1 = ( V_i * 2 – 1 ) / 3,                                                                                                      (3а)

где  V_i+1  - последующее нечётное число ветки.

Ветка заканчивается тогда, когда очередное число V_i+1 не будет целым числом.

В частности, нижняя ветка  от основного ствола будет иметь вид: 4, 1.

То есть, эта ветка как бы «зацикливается» с основанием основного ствола.

Далее имеем ветки:

     16, 5, 3,

     64, 21,

     256, 85,

     1024, 341, 227, 151,  

     и так далее.

В дальнейшем, при обозначении каждой ветке будут указываться чётное число «крепления» ветки к стволу и только нечётные числа согласно (3а).

 

Задача 3. Построение боковых стволов графа.

От почти каждого числа Х на ветках могут быть построены стволы, которые определяются уравнением, аналогичным (2).

     V_i= Х * 2^k,                                                                                                               (4)

где i – номер числа в последовательности Коллатца,

k – натуральное число,

V_i – место «крепление» очередной ветки на данном стволе.

Используя уравнение (4), можно построить ствол от числа 5, который будет иметь следующие числа «крепления» веток:

     40, 160, 640, 2560, и т.д.

И, в свою очередь, на этом стволе будут следующие ветки:

     40, 13,

     160, 53, 35, 23, 15,

     640, 213,

     2560, 853, и т.д.

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

Если рассматривать различные ветки всего ориентированного графа  чисел Коллатца, то можно заметить следующие особенности:

- ветка начинается с «места крепления» в виде чётного числа;

- ветка заканчивается нечётным числом, которое имеет два вида: либо 3 * k, либо 6 * k + 1, где k – натуральное число;

- остальные нечётные числа ветки имеют вид 6 * k + 5, где k – натуральное число.

Важно заметить:

На числах вида 3 * k, где k – натуральное число, нельзя построить ствол. Ведь при любом умножении этих чисел на числа 2ⁿ, где n – натуральное число, с последующим отнятием числа 1 никогда не получится число, которое делится на число 3.

 

Задача 4. Построение последовательности Коллатца с использованием ориентированного графа.

Определение последовательности Коллатца при наличии ориентированного графа чисел  происходит следующим образом.

На ориентированном графе чисел находится нечётное число, с которого начинается последовательность Коллатца.

Допустим, это число находится на ветке 1.

Далее по ветке 1 направляемся к точке «крепления» ветки 1 со стволом 1.

Далее по стволу 1 попадаем на ветку 2.

Далее по ветке 2 направляемся к точке «крепления» ветки 2 со стволом 2.

И так далее.

Если построен ориентированный граф чисел, то можно иначе записать последовательность нечётных чисел Коллатца, которая начинается с числа 1 и заканчивая числом 27:

    основной ствол 1, ветка 16, 5,

    ствол 5, ветка 160, 53, 35, 23,

    ствол 23, ветка 184, 61,

    ствол 61, ветка 976, 325,

    ствол 325, ветка 1300, 433,

    ствол 433, ветка 1732, 577,

    ствол 577, ветка 9232, 3077,2051, 1367, 911,

    ствол 911, ветка 7288, 2429,

    ствол 2429, ветка 4858, 1619,

    ствол 1619, ветка 3238, 1079, 719, 479, 319,

    ствол 319, ветка 1276, 425, 283,

    ствол 283, ветка 1132, 377, 251, 167,

    ствол 167, ветка 1336, 445,

    ствол 445, ветка 1780, 593, 395, 263, 175,

    ствол 175, ветка 700, 233, 155, 103,

    ствол 103, ветка 412, 137, 91,

    ствол 91, ветка 364, 121,

    ствол 121, ветка 484, 107, 71, 47, 31,

    ствол 31, ветка 124, 41, 27.

 

Задача 5. Определение размеров стволов и веток ориентированного графа Коллатца.

Согласно (2) и (4) все стволы ориентированного графа будут бесконечны, так как число k – бесконечно.

Размер ветки определяет конечное число на этой ветке.

Если конечное число на ветке будет:

     2^k1 - 1,

где k1 – натуральное число,

то на этой ветке будет не менее k1 нечётных чисел.

Если выбирать очень большое число k1, то можно получить очень большую ветвь.

 

Выводы.

Показаны принципы построение ориентированного графа чисел, которые используются в последовательностях Коллатца.

1. Открытые математические проблемы. https://ru.wikipedia.org/wiki/Открытые_математические_проблемы (дата обращения 17.10.2024)
2. Гипотеза Коллатца. https://ru.wikipedia.org/wiki/Гипотеза_Коллатца (дата обращения 17.10.2024).

Комментарии пользователей:

28.10.2024, 16:44 Цорин Борис Иосифович Отзыв: {1} Работа [3], "в развитие которой" идет статья, - статья на википедии? Однако ж. {2} Статья не имеет ценности. Никакой. Долгое-долгое словоблудие про стволы и ветки с нарушением терминологии, связанной с деревьями, в итоге свелось к тривиальному результату. Всю статью можно сократить до одной фразы: "Числа вида 3n+1 не могут делиться на 3, а деление на 2 четного числа, не делящегося на 3, дает число, не делящееся на 3, поэтому в любой сиракузской последовательности число, делящееся на 3, может стоять исключительно в начале последовательности".

5.11.2024, 8:21 Усов Геннадий Григорьевич Отзыв: {1}Убрал работу [3]. {2}Непонятно, что имелось под "нарушением терминологии". То что я вместо суков дерева называл эти обьекты стволами? При "сокращении статьи" рецензент не увидел, что приведены принципы построение дерева: как формируется ветвь и как формируются на ветви стволы.

5.11.2024, 13:25 Цорин Борис Иосифович Отзыв: "Нарушение терминологии" - то, что Вы называете деревом нечто, деревом не являющееся. Если ветви связаны между собой "двумя стволами: боковым и основным", то это уже не дерево. Но это мелочь по сравнению с тем, на что Вы не ответили: что все Ваше "построение дерева" в итоге привело к тривиальному результату и, следовательно, оказалось бессмысленным. Ну давайте еще писать статьи, в которых будет "Научная новизна: гипотеза Коллатца в очередной раз не доказана" или "Научная новизна: проверено пять случайных чисел, для них гипотеза Коллатца выполнилась". Я утрирую, конечно, но Ваше "замечание" от этого ушло недалеко, и доказывается одним предложением, а не Вашим "деревом".

5.11.2024, 15:15 Усов Геннадий Григорьевич Отзыв: И вновь Вы не поняли "структуру" дерева. Там нет двух стволов, которые связывают две ветви! На каждой ветви будут стволы у каждого нечётного числа, за исключением числа, которое делится на 3. И для каждого такого ствола будут различные ветви! Причём таких ветвей на каждом стволе будет бесчисленное множество.

5.11.2024, 15:17 Усов Геннадий Григорьевич Отзыв: Кстати, в статье ничего не говорится о доказательстве гипотезы Коллатца, за исключением введения. Что-то Вас разобрало...

5.11.2024, 19:11 Цорин Борис Иосифович Отзыв: {1} "Там нет двух стволов, которые связывают две ветви!" - как же нет? Цитирую: "Ветки могут быть связаны между собой некоторыми так называемыми боковыми стволами", плюс основной ствол - вот Вам и замкнутый маршрут по Вашему графу. {2} "Кстати, в статье ничего не говорится о доказательстве гипотезы Коллатца" - кажется, Вы так и не поняли основное мое замечание к статье. Перечитайте последнее предложение первого моего отзыва.

6.11.2024, 7:23 Усов Геннадий Григорьевич Отзыв: {1} Во-первых, "плюс основной ствол" - это уже Вы добавили. Во-вторых, если последовательность "попадает" на основной ствол, то она по этому стволу "попадает прямо на 1". То есть, для этой последовательности верна гипотеза.

6.11.2024, 14:43 Соловьёв Виктор Григорьевич Отзыв: Геннадий Григорьевич! Я внимательно также читаю Вашу оригинальную статью. А поскольку, по Вашему признанию, Вы читаете и мою статью, то в этом смысле мы с Вами коллеги по данной теме. В какой-то мере данная статья дополняет или даже расширяет работу казахстанского ученого Курмет Султана, который строит граф в виде дерева, построенное на числе 1, и которое представляет собой действие, обратное действию гипотезы Коллатца. В его работе есть даже глава "2. Обратное вычисление". Курмет Султан этими рассуждениями пытается доказать гипотезу, у Вас же более тонкое понимание проблемы, поэтому Вы и пишите, что "в статье ничего не говорится о доказательстве гипотезы Коллатца" (Ваша цитата). Если для Вас это представляет интерес, то полная ссылка на работу приведена в моей статье под номером 4. А вот ссылка на отдельный pdf-файл из этой работы - https://vixra.org/pdf/1708.0177v3.pdf

6.11.2024, 15:53 Цорин Борис Иосифович Отзыв: Уххх... Определение: дерево - это связный граф без циклов. Если Вы возьмете любое дерево и свяжете две его ветви "боковым стволом" или чем-то еще, оно перестанет быть деревом. Так понятнее? И Вы упорно игнорируете основное замечание, пытаясь оспорить второстепенное.

6.11.2024, 16:19 Усов Геннадий Григорьевич Отзыв: Виктор Григорьевич! Спасибо за сообщение! Кстати, а Вы согласны с статьёй Курмет Султана? Что он доказал?

6.11.2024, 17:39 Цорин Борис Иосифович Отзыв: "Что он доказал?" - о, я Вам расскажу вместо Виктора Григорьевича, хотя и спасибо ему за ссылку, снова посмеялся. Кстати, первая "теорема" Кермет Султана - это Ваше "замечание", только разумно доказанное, без длинных деревьев. Так что не только научности, но и новизны в Вашем "замечании" нет. А вот дальше... Дальше там на страницах 8-10 грубая логическая ошибка. Из утверждения "Если уравнение "k=F(x)-18t неразрешимо в целых числах, то уравнение k+18t=F(x) неразрешимо в целых числах", где k и t - параметры, он махом перескакивает к "если уравнение k=F(x) неразрешимо в целых числах, то k+18t=F(x) неразрешимо в целых числах". Так он ошибочно решил, что доказал отсутствие циклов, не включающих единицу. А на страницах 12-13 он из "в графе бесконечное количество вершин, соответствующих различным числам" перескочил к "в графе есть вершины, соответствующие всем числам". Так он ошибочно решил, что доказал отсутствие бесконечно возрастающих сиракузских последовательностей. Итого де-факто Кермет Султан доказал примерно такое же ничего, как и Вы, только ту часть ничего, которую доказывали Вы, он доказал более лаконично.

6.11.2024, 17:48 Соловьёв Виктор Григорьевич Отзыв: Геннадий Григорьевич! Отвечая на Ваш вопрос, отмечаю, что как раз в своей статье критически рассмотрел доказательство Курмет Султана и считаю, что его утверждение не верно или верно лишь частично. Единственное, я думаю, что с помощью графов реально доказать тот факт, что любая последовательность Коллатца непременно зацикливается. Во всяком случае, на этом принципе построены доказательства, приведенные в очень большом количестве англоязычных работ. Они легко находятся в интернете, например, на ресурсе https://www.academia.edu. А вот тот факт, что она зацикливается исключительно на 4-2-1 необходимо доказывать (что я и попытался сделать, впрочем эта тема не относится к данной). Только эти 2 условия необходимы и достаточны, чтобы признать гипотезу Коллатца состоятельной. Что касается Вашей статьи, то Ваши "замечания" в ней, помогут уточнить теорию графов в этой области.

6.11.2024, 19:16 Усов Геннадий Григорьевич Отзыв: Борис Иосифович! Вы говорите: "Если Вы возьмете любое дерево и свяжете две его ветви "боковым стволом" или чем-то еще, оно перестанет быть деревом. " Да, так строится обычное дерево. А здесь дерево другое: есть стволы между ветвями! Так удобнее разделить два процесса: - если n - нечётное число, то число n умножается на число 3 и добавляется число 1, И - если n - чётное число, то число n делится на число 2. Можно назвать это упорядоченным графом. Мне без разницы. Разделение необходимо для понимания процесса гипотезы.

6.11.2024, 19:54 Цорин Борис Иосифович Отзыв: "Можно назвать это упорядоченным графом" - ориентированным. "Разделение необходимо для понимания процесса гипотезы" - а теперь все-таки перейдем к основной проблеме. Ваше "замечание к гипотезе", выдвинутое на основе "понимания процесса": а) тривиально; б) было ранее сформулировано другими доказывальщиками (и не исключаю, что десятками, но один пример Вам вон привели, Кермет Султана); в) доказывается одним предложением вместо трех страниц рассуждения про стволы.

7.11.2024, 11:10 Усов Геннадий Григорьевич Отзыв: Борис Иосифович, спасибо за подсказку! Изменил название, аннотацию, немного перестроил статью, убрал замечание и добавил оценку размеров стволов и веток.

7.11.2024, 14:56 Цорин Борис Иосифович Отзыв: После удаления "замечания" статья пришла к типовому для Вашего творчества виду: "покрутили-повертели, ничего не нашли, но на всякий случай опубликовали". Вот представьте себе, сдают школьники на уроке труда сделанные из дерева кто табуретку, кто скворечник... А один приносит кучу опилок и называет это "поиск способов изготовить ядерный реактор из осины". Ну не получилось, но какие цели были поставлены! И все бы ничего, но он свято уверен, что кому-нибудь когда-нибудь его опилки помогут изготовить ядерный реактор, поэтому на следующий урок он повторит этот титанический труд с другим сортом древесины.

8.11.2024, 7:40 Усов Геннадий Григорьевич Отзыв: Уважаемый Борис Иосифович! Как Вы далеко отстали от действительности. Вы не представляете, что можно сделать из простых древесных опилок!

8.11.2024, 14:54 Цорин Борис Иосифович Отзыв: Можно-можно. Только вот изготовление опилок не является важной частью этого процесса, и опилки сами по себе не стоят больше, чем древесина, из которой они получились.

8.11.2024, 17:51 Усов Геннадий Григорьевич Отзыв: И вновь Вы отстаёте от действительности. Срубить и продать дерево - это одна цена. А сделать из этого дерева опилки (есть такие производства) - это уже добавленная стоимость.

9.11.2024, 8:56 Цорин Борис Иосифович Отзыв: Ну посмотрите в Интернете цены на кубометр древесины и цены на кубометр опилок. Ну и считайте, что по массе примерно древесина вдвое больше опилок. Я, например, древесину самую дешевую (дрова) у себя в области нашел по 1300 за м3, а опилки удалось найти по 300 за м3.

9.11.2024, 13:14 Усов Геннадий Григорьевич Отзыв: Древесные опилки (березовые) сухие, стружка, наполнитель для животных, теплиц 6 кг. На ОЗОНе по 828р. Как то так...

9.11.2024, 14:18 Цорин Борис Иосифович Отзыв: О да, если постараться, можно и по 8000 найти. Я о самых дешевых говорю, а не о самых дорогих. Упаковка, доставка, оплата маркетплейса, - все это повышает цену. Вы б еще в зоомагазинах цены смотрели на опилки, да на полукилограммовые упаковки. Вы смотрите цены там, где кубометрами торгуют. На авито вон посмотрите.

9.11.2024, 17:28 Усов Геннадий Григорьевич Отзыв: Уважаемый Борис Иосифович! Вы путаете отходы с фабрикатом! Кому что нужно...

12.11.2024, 9:49 Цорин Борис Иосифович Отзыв: Видите ли, если "сделал что мог, получились вот такие опилки, выложу для всех" - то это именно с отходами и надо сравнивать.

12.11.2024, 10:52 Цорин Борис Иосифович Отзыв: Кстати, то, что Вы считаете фабрикатом на озоне, - это те же самые отходы, только просеянные, отсортированные по размеру и упакованные. Я не слышал, чтоб кто-либо изготавливал опилки из древесины целенаправленно, пуская закупаемую древесину на опилки целиком.

12.11.2024, 13:48 Усов Геннадий Григорьевич Отзыв: В Красногорске есть Тиги-Кнауф. Вот раньше в Тиги привозили чурбаки (видел дерево, распиленное на чурбаки) и делали утеплитель - цементно-стружечные плиты 50 * 150 (кажется). Далее: когда выпускаю ДСП для столов и прочей мебели, то забирают у соседней лесопилки отходы или как?

12.11.2024, 16:13 Цорин Борис Иосифович Отзыв: А что, фанеру Тиги-Кнауф больше не производит? Обычно в ДСП и ЦСП пускают то, что получается отходами при изготовлении фанеры. Ну и да, лесопилка отходы не сжигает. Некоторые виды стружки могут изготавливать и целенаправленно из других отходов (из кряжа, корней, веток, сучьев), но не как "фабрикат", а именно как "полуфабрикат". Некоторые виды стружки, но не конкретно опилки. Откройте хоть в википедии статьи "стружка" и "опилки" и сравните значения этих слов.

12.11.2024, 18:39 Усов Геннадий Григорьевич Отзыв: Теперь вернёмся к Вашему ошибочному суждению: "и опилки сами по себе не стоят больше, чем древесина, из которой они получились." - Наверное, опилки и стружка стоят дороже, чем то дерево, из которого они произведены. Ведь по Вашему: "из других отходов (из кряжа, корней, веток, сучьев)". Раз из этих отходов что-то делают, то, согласно нашей экономики, эти отходы чего-то стоят. Следовательно, сначала произвели отходы, а у них есть некоторая цена, а затем опилки - добавленная стоимость.

13.11.2024, 6:39 Цорин Борис Иосифович Отзыв: Читайте внимательнее. Некоторые виды стружки. Но не опилки. У опилок есть четкое определение. Опилки - отходы при пилении.

13.11.2024, 8:44 Усов Геннадий Григорьевич Отзыв: Хорошо, со стружками мы разобрались. Это - добавленная стоимость. Теперь об опилках. Вы "грамотно" пропустили мою фразу: "когда выпускают ДСП для столов и прочей мебели, то забирают у соседней лесопилки отходы или как?" И чем это отличается от стружки?

13.11.2024, 16:31 Цорин Борис Иосифович Отзыв: Почему пропустил? Сказал. Повторяю: "Обычно в ДСП и ЦСП пускают то, что получается отходами при изготовлении фанеры". Но могут и у лесопилки отходы брать. И вторсырье в измельчитель пускать. Но уж точно не закупают на озоне фасовку по стократной цене и не закупают промышленный лес для превращения в стружку. Не окупится, знаете ли.

13.11.2024, 17:38 Усов Геннадий Григорьевич Отзыв: Напоминаю, что фанеру делают путем склеивания шпонов. А те, в свою очередь, делаются, как правило (дешевый способ), путем СРЕЗАНИЯ листов с бревен, например, при вращении бревна. И там почти нет опилок... Насчёт лесопилки ... Вряд ли на дсп пускают кору деревьев. Следовательно, бревна под нужные опилки готовят.

13.11.2024, 18:13 Цорин Борис Иосифович Отзыв: Охх... Как же с Вами тяжело... Даже погуглить не можете. Отходы - не только опилки. Отходы покрупнее пускают в измельчитель. Бревна "под опилки" не готовят. На измельчение пускают то, что нереально продать. "Добавочная стоимость" Ваша добавляется в этом случае к нулю. Ок, раз Вам так хочется занудствовать, уточняю формулировку: вместо "опилки сами по себе не стоят больше, чем древесина, из которой они получились" прошу читать "опилки сами по себе не стоят больше, чем древесина, из отходов при обработке которой они получились, хотя порой и больше, чем отходы в чистом виде". Так Вас устроит?

14.11.2024, 7:06 Усов Геннадий Григорьевич Отзыв: Охх.. И с Вами не легче... Устроит. Немного разобрался: что такое фанера. Мне кажется, что лучше возить не кучу сучьев, а что-то более крупное с точки зрения уменьшения денежных затрат на перевозку, хранение и подачу сырья на измельчитель. Кстати, эти мероприятия входят в "добавочную стоимость".

Оставить комментарий