Дальнейшие исследования гипотезы Коллатца с целью её доказательства

УДК 511

Введение

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

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

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

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

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

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

Формулировка гипотезы Коллатца [3]:

какие бы начальные числа n не выбирались, рано и поздно числом последовательности будет число 1.

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

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

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

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

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

В результате получается последовательность чисел, последним числом которой будет число 1.

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

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

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

Цели и задачи

В данной статье были продолжены исследования последовательностей Коллатца в развитие [3]. В процессе этих исследований был решен ряд задач.

Задача 1. Построение модели ветвей дерева для гипотезы Коллатца.

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

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

Сначала определяется ствол дерева или 1-я ветка с номером V1 (1 – номер ветки). С учетом формул (1) получается последовательность Коллатца, состоящая из следующих чисел:

    V1(k) = 2 ^ k,                                                                                                    (3)  

где k >= 0 – целое число.

Назовём ветку V1 веткой нулевого уровня для последовательностей Коллатца.

На ветке V1 располагаются ветки на тех числах V1(k), для которых справедливо условие:

    (V1(k) – 1) mod 3 = 0.

Тогда номер новой ветки будет:

    A = (V1(k) – 1) / 3                                                                                            (4)

Следовательно, получаем новую ветку с номером А (нечётное число):

    VA(k) = A * 2 ^ kа,                                                                                           (4а)

где kа  >= 0 – целое число.  

Таким образом, на стволе дерева можно построить ветки:

     V1-4, V5-16, V21-64, V85-256, V341-1024, V1365-4096, и т.д.                    (5)                                      

То есть, ветки будут построены на стволе через каждые 2 шага последовательности (2).

Эти ветки составляют первый уровень для последовательностей Коллатца.

Аналогично можно построить ветки второго уровеня для последовательностей Коллатца:

- для ветки V5-16 получаем ветки V3-10, V13-40, V53-160, V213-640, и т.д.

- для ветки V85-256 получаем ветки V113-340, V453-1360, V1813-5440,  и т.д.

- для ветки V341-1024 получаем ветки V227-682, V909-2727, V3637-10912,  и т.д.

и т.д.

Для веток V21-64 и V1365-4096 (а также для веток далее с шагом 3 на стволе дерева) новые ветки построить нельзя, так как нельзя от числа, которое делится на 3, отнять 1 и получить число, которое делится на 3. Эти ветки будут существовать без новых веток.

Ветка V1-4 имеет особый статус. Она даёт возможность не заканчивать процесс прихода к числу 1, а продолжить процесс нахождения чисел:

16, 8, 4, 2, 1, 4, 2, 1, 4. 2, 1, 4, 2. 1,… и т.д.

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

Любую последовательность Коллатца можно построить, если применить полученную модель веток дерева. Тогда последовательность Коллатца будет располагаться на некоторой последовательности веток дерева, или состоять из последовательности номеров этих веток согласно (1).

Задача 2. Представление всех натуральных чисел на ветках дерева.

Определённая выше модель веток дерева позволяет «расположить» все множество натуральных чисел на ветках этого дерева, основанием которого является число 1.

Докажем это.

Каждое натуральное число N можно представить единственным способом в виде:

      N = А * 2 ^ k, где А - нечётное число, k >= 0 – целое число.                        (9)

Поскольку ветки с числами можно построить для любого нечётного положительного числа, то выражение (9) совпадает с представлением веток для последовательностей Коллатца (4а).

Следовательно, на всех ветках для последовательностей Коллатца расположены все натуральные числа.

Задача 3. Представление на дереве всех возможных веток.

Допустим, есть одна ветка VH, для которой не существует места на модели веток дерева.

Тогда, согласно уравнениям (1), для числа Н следующим числом в последовательности Коллатца будет число М:

     М = 3 * Н + 1

Число М – чётное, которое можно представить в виде:

     М = В * 2 ^ t, где В – нечётное число, и t >= 0 – целое число.

Таким образом, для ветки VH найдено место на ветке VВ.

Аналогично, можно рассмотреть существования места на дереве для нескольких веток.

Задача 4. О построении «кольца» из нескольких веток.

Поскольку все ветки «построены» от числа 1, то можно «пройти» от любого числа на любой ветке к числу 1 по некоторой последовательности веток.

Допустим, есть несколько веток, которые определяются друг относительно друга, но эти ветки образуют замкнутую последовательность вне дерева.

Допустим их число g, и это последовательность веток, которые не находятся на дереве:

          VG1, VG2, VG3, … , VGg   

причем, ветка VG1 находится на ветке VG2, ветка VG2 находится на ветке VG3, и т. д.

И при этом ветка VGg находится на ветке VG1.

Согласно (9):

     G2 * 2 ^ a1 = G1 * 3 + 1                                                                 (9а)

     G3 * 2 ^ a2 = G2 * 3 + 1                                                                 (9b)

Предположим, что ветка VG3 находится на ветке VG1, то есть имеет место кольцо.

Тогда имеет место уравнение:

     G1 * 2 ^ а3 = G3 * 3 + 1                                                                   (9с)

Можно найти упростить уравнения (9а), (9b), (9с). Для этого в уравнение (9b) подставим значения G1 и G3 из уравнений (9а) и (9с). Получается:

     G2 * (2^a1 * 2^a2 * 2^a3 – 27) = 9 + 3 * 2^a1 + 2^a2 * 2^a3          (9d)

Как видно из правой части уравнения (9d) должно выполняться условие для суммы показателей степени 2:

     А = a1 + а2 + а3 > 4

При больших показателях степени с величиной  2^a1 * 2^a2 * 2^a3 может сравниться только величина 3 * 2^a1, однако величина  2^a1 * 2^a2 * 2^a3 ещё умножается на величину G2.

Поэтому при больших значениях величины G2 левая часть уравнения (9d) будет больше её правой части. А при малых значениях величины G2, как известно, кольца быть не может, так как уже были расчёты.

Таким образом, ветка VG3 не может находиться на ветке VG1.

Данный процесс можно продолжить дальше, сравнивая числа Gi, начиная с ветки VG4 до ветки VGg, с числом G1. И каждый раз необходимо проверять условия, аналогичные условию (9d).

Задача 5. Определение времени остановки для всех натуральных чисел.

Рихо Террас доказал[3], что почти каждое натуральное число имеет конечное время остановки при построении последовательности Коллатца.  Другими словами, почти каждая последовательность Коллатца VH достигает точки или числа U, которое находится строго ниже своего начального значения или U < H. 

В частности, для начальных чисел до 50:

3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49,

существует время остановки, которое наступает через следующее количество шагов:

2, 1, 4, 1,  3,    1,   4,   1,   2,   1,   3,   1,  37,  1, 35,  1,   2,   1,   5,   1,   3,   1,   34,  1,   (10)

В частности, для последовательности V27 первое число, меньшее 27, встречается через 37 шагов.

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

Тогда можно построить эвристические алгоритмы для определения начальных чисел, для которых имеет место одинаковое количество шагов до времени остановки.

В частности:

- шаги 1 будут у чисел, где начальное число 5 (всего 1), и числа с интервалом 4;

- шаги 2 будут у чисел, где начальное число 3 (всего 1), и числа с интервалом 16;

- шаги 3 будут у чисел, где начальные числа 11 и 23 (всего 2), и числа с интервалом 32;

- шаги 4 будут у чисел, где начальные числа 7, 15, 59 (всего 3), и числа с интервалом 128;

- шаги 5 будут у чисел, где начальные числа 39, 79, 95, 123, 175, 199, 219, (всего 7), и числа с интервалом 256;

Такие вычисления можно продолжить далее для всех натуральных чисел.

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

В частности, шаги 37, как у числа 27, будут у чисел с интервалом 2^56.

Задача 6. О стремлении всех последовательностей Коллатца к числу 1.

Теперь можно показать, что почти все (согласно Рихо Терраса) последовательности Коллатца стремятся к числу 1.

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

Тогда для почти каждого "начального" числа в последовательности Коллатца согласно доказательству Рихо Террас, а также согласно расчётам в задаче 5, найдётся число, которое будет меньшее "начального" (время остановки).

Получается, что для почти каждого "начального" числа не есть минимальное число, для которого неверна гипотеза Коллатца.

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

Существуют числа, для которых при построении последовательности Коллатца n( i ) из (1) получаются подряд либо несколько увеличений последующих чисел, либо несколько уменьшений последующих чисел.

Для чётных чисел получается:

- если число n(1) равно 2 + 4 * К, где К >= 0, то число n(2) будет нечётным. И тогда число n(2) = 1/2 * n(1);

- если число n(1) равно 4 + 8 * К, где К >= 0, то только число n(3) будет нечётным. И тогда число n(3) = 1/4 * n(1);

- если число n(1) равно 8 + 16 * К, где К >= 0, то только число n(4) будет нечётным. И тогда число n(4) = 1/8 * n(1);

- если число n(1) равно 16 + 32 * К, где К >= 0, то только число n(5) будет нечётным. И тогда число n(5) = 1/16 * n(1).

И т.д.

Для нечётных чисел получается:

- если число n(1) равно 1 + 4 * К, где К >= 0, то число n(2) будет чётным. И тогда число n(2) = 3/2 * n(1) (примерно);

- если число n(1) равно 3 + 8 * К, где К >= 0, то только число n(3) будет чётным. И тогда число n(3) = 9/4 * n(1) (примерно);

- если число n(1) равно 7 + 16 * К, где К >= 0, то только число n(4) будет чётным. И тогда число n(4) = 27/8 * n(1) (примерно);

- если число n(1) равно 15 + 32 * К, где К >= 0, то только число n(5) будет чётным. И тогда число n(5) = 81/16 * n(1) (примерно).

И т.д.

Количество чётных и нечётных чисел одинаковое. Причём одинаковы эти числа по шагам повторений.

Для чётных чисел уменьшение чисел в последовательности происходит на величину степени числа 2.

Для нечётных увеличение чисел в последовательности происходит на величину степени числа 1,5 (приблизительно).

Поэтому определяющим в стремлении чисел последовательности к числу 1 являются чётные числа.

Задача 8. Построение на компьютере дерева для последовательностей Коллатца.

Теперь можно строить конкретное дерево для последовательностей Коллатца на основании полученной модели.

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

Определим некоторое чётное число М, которое будет обозначать, что при построении дерева будут рассматриваться только нечётные числа, меньшие М. Число М будет зависеть от возможности компьютера построить дерево за реальное время.

Следовательно, в уравнениях (4) и (4а) будет:

     VA(k) < M, А < M                                                                                                (11)

Ветки, номера которых не превышают числа М, «складируются» на некотором складе (база данных). На каждой из этих веток остаются натуральные числа, которые не превышают числа М.

Получается, что на «складе» подготовлены все ветки, удовлетворяющие (11).

Теперь можно собирать дерево.

Основной ствол – это ветка с номером 1.

На этой ветке есть номера последующих веток, приведённые в (7) и (8).

Аналогично отбираются на «складе» новые ветки для уже установленных веток.

Данный процесс можно продолжить до тех пор, пока не будут установлены все ветки со «склада».

При этом получится следующая картина: на ветках дерева будут не все числа от 1 до М.

Например, если взять число М = 1000, то на ветках дерева не будет числа 27 (числа от 1 до 26 – присутствуют). Это связано с тем, что для того, чтобы от ствола по веткам дерева «добраться» до числа 27, необходимо перемещаться по 41 ветке. Причём, одна из этих веток имеет номер 3077, то есть, больше, чем М.

Если взять число М = 4000, то на ветках дерева не будет числа 255 (числа от 1 до 254 – присутствуют). Здесь имеет место 15 веток, и одна из веток имеет номер 4373.

Далее, при М = 5000 нет числа 447, здесь 34 и 13121,

при М = 14000 нет числа 703, здесь 62 и 83501,

при М = 90000 нет числа 1819, здесь 58 и 425645,

при М = 600000 нет числа 4255, здесь 73 и 2270045,

при М = 2400000 нет числа 4591, здесь 61 и 2717873,

Данные расчёты можно продолжить, и увеличивая число М, можно расставить на ветвях дерева большее количество натуральных чисел, которые идут подряд, начиная с 1.

Выводы.

Построена модель веток дерева для последовательностей Коллатца.

На ветках дерева будут представлены все натуральные числа.

Для каждой ветки существует место на модели веток дерева.

Время остановки для небольших натуральных чисел повторяется с определённым интервалом для натуральных чисел.

Научная новизна.

Определена модель веток дерева для последовательностей Коллатца.

Получены новые исследования по гипотезе Коллатца.

Рецензии:

22.07.2021, 0:50 Мирмович Эдуард Григорьевич
Рецензия: Автор затронул т.н. "сиракузскую проблему", относящуюся к нерешённым задачам математики. По этой проблеме 12 лет назад был запущен проект добровольных распределённых вычислений «Collatz Conjecture», целью которого является проверка гипотезы Коллатца на больших числах. Кроме этого проекта, ровно 4 года назад поиском решения этой проблемы стал проект распределённых вычислений (http://www.rechenkraft.net/yoyo/). Интересно, что графики последовательностей этих чисел (автор не приводит) похожи на траектории движения градин в атмосфере, их даже назвали: числа-градины. В 1985 году по этой проблеме была интересная публикация в журнале American Mathematical Monthly Джефа Лагарьяса: The 3x+1 problem and its generalizations. Рецензент навскидку привёл факты, о которых в статье доказательного статуса ничего не говорится, будто автор впервые занялся и решил эту проблему. Рецензент не считает наспех (за один день пробега по электронным ресурсам) скомпиллированную статью, где большая часть - это копир из Википедии, при этом, само доказательство содержится в нескольких словах, достойной публикации в научном журнале в представленном виде. Вот если бы она была покороче, без явных переписок из википедии, да ещё с аналогом в другой системе счисления... рецензент был бы за её публикацию. А пока следует дождаться других двух положительных рецензии.