Публикация научных статей.
Вход на сайт
E-mail:
Пароль:
Запомнить
Регистрация/
Забыли пароль?
Научные направления
Поделиться:
Разделы: Математика
Размещена 20.07.2021. Последняя правка: 23.07.2021.
Просмотров - 115

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

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

к.т.н.

МГУ, 1972

пенсионер

Аннотация:
Определена модель ветвей дерева для последовательностей Коллатца. Доказана гипотеза Коллатца с помощью модели ветвей дерева для последовательностей Коллатца.


Abstract:
A tree branch model for Collatz sequences is defined. The Collatz conjecture is proved using the tree branch model for Collatz sequences.


Ключевые слова:
гипотеза Коллатца; натуральное число; модуль числа

Keywords:
Collatz hypothesis; natural number; the absolute value of a number


УДК 511

Введение

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

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

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

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

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

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

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

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

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

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

Построение последовательности Коллатца можно представить следующими формулами:

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

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

Поскольку первое условие в (1) позволяет получить только чётное число, условия (1) упрощаются[3]:

- если:  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.

 

Простой пример:

для числа 3, согласно (1), получена следующая последовательность Коллатца:

3, 10, 5, 16, 8, 4, 2, 1.

Всего здесь получается 7 шагов (чисел в последовательности) с целью получения числа 1.

Далее, начиная с 1, начинается циклическое повторение:

1, 4, 2, 1, 4, 2, 1, 4, 2. 1,…

Для числа 19 получается 20 шагов с целью получения числа 1, а для числа 27 получается 111 шагов с целью получения числа 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).

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

 

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

Так же, как при поиске веток на стволе дерева, можно найти ветки и на ветках первого уровня (5), а именно:

- для ветки 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,… и т.д.

Таким образом, сформирован второй уровень для последовательностей Коллатца:

- V3-10, V13-40, V53-160, V213-640, V853-2560, и т.д.,

- V113-340, V453-1360, V1813-5440,  и т.д.

- V227-682, V909-2727, V3637-10912, и т.д                                                         (6)

 

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

Любую последовательность Коллатца можно построить, если применить полученную модель веток дерева. Тогда последовательность Коллатца будет располагаться на некоторой последовательности веток дерева, или состоять из последовательности номеров этих веток согласно (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

     G3 * 2 ^ a2 = G2 * 3 + 1

Из этих двух уравнений получается уравнение:

     G3 = ((G1 * 9 + 3 + 2 ^ a1) / 2 ^ (а1 + a2)

Из этого уравнения видно, что ветка VG3 не находится на ветке VG1, так как иначе бы было соотношение:

    G1 * 2 ^ k = G3 * 3 + 1, k >= 0 – целое число.

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

Следовательно, не существует замкнутая последовательность веток вне дерева.

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

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

Например, ветка VA1 будет опираться на ветку VA2, а ветка VA2, в свою очередь, будет опираться на некоторую ветку VА3.

И этот процесс будет продолжаться до тех пор, пока очередной веткой не будет ветка V1. Только тогда у очередной ветки VAi не будет ветки, на которую ветка VAi опирается.

То есть, новое дерево есть часть дерева для последовательностей Коллатца.

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

 

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

Согласно (1а), для числа n(2) есть два варианта при наличии n(1): либо n(2) по сравнению с n(1) за один шаг увеличивается почти в 3/2 раза, либо n(2) по сравнению с n(1) за один шаг уменьшается в 1/2 раза.

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

В частности, есть числа первого вида:

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

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

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

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

И т.д.

С другой стороны, есть числа второго вида:

- если число n(1) равно 3 + 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.

 

Задача 9. Доказательство гипотезы Коллатца.

В задаче 1 была построена модель веток дерева для последовательностей Коллатца.

В задачах 2, 3, 4 было показано, что:

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

- все возможные ветки с натуральными числами будут находиться на дереве для последовательностей Коллатца;

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

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

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

Что доказывает гипотезу Коллатца.

Кроме того, в задаче 5 подтверждено доказательство Рихо Терраса о том, что почти каждое натуральное число имеет конечное время остановки при построении последовательности Коллатца. Время остановки - это число в последовательности Коллатца, меньшее начального числа, Подтверждение основано на повторяющихся с определённым интервалом одинаковых значениях времени остановки для почти всех натуральных чисел.

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

Что тоже доказывает гипотезу Коллатца.


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

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

Доказана гипотеза Коллатца с помощью модели веток дерева.

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

Выводы.

Доказана гипотеза Коллатца с помощью модели веток дерева для последовательностей Коллатца.

Библиографический список:

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




Рецензии:

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. Рецензент навскидку привёл факты, о которых в статье доказательного статуса ничего не говорится, будто автор впервые занялся и решил эту проблему. Рецензент не считает наспех (за один день пробега по электронным ресурсам) скомпиллированную статью, где большая часть - это копир из Википедии, при этом, само доказательство содержится в нескольких словах, достойной публикации в научном журнале в представленном виде. Вот если бы она была покороче, без явных переписок из википедии, да ещё с аналогом в другой системе счисления... рецензент был бы за её публикацию. А пока следует дождаться других двух положительных рецензии.

22.07.2021 14:14 Ответ на рецензию автора Усов Геннадий Григорьевич:
Уважаемый Эдуард Григорьевич! Благодарю Вас за рецензию к моей статье! Далее по замечаниям в рецензии. Статья Джефа Лагарьяса приведена в числе многих работ в [3], поэтому я не стал её отдельно рассматривать, поскольку выводы этой статьи были учтены в [3] (там ещё много других статей по проблеме). О числах-градинах не стал упоминать, поскольку это одно из интересных исследований по гипотезе, однако оно не даёт дополнительную информацию для решения проблемы Коллатца. Я не стал упоминать работы по рассмотрению последовательностей Коллатца в двоичной системе, поскольку это тоже не ведёт к решению проблемы Коллатца. Статья должна быть не очень длинной, а подобных направлений исследований приведено в [3] в количестве более 10. Я привёл в статье результаты вычислений на ЭВМ по проверке чисел на гипотезу Коллатца. В статье можно значительно сократить эти результаты, хотя они могут лучше объяснить «поведение» последовательностей Коллатца. И данные результаты ранее не приводились в таком виде. В начале статьи есть места, которые почти повторяют известные места из Википедии. Но это необходимо только для постановки задачи: постановка задачи единая для всех. Может быть, из этого что-то можно сократить. Теперь о новизне статьи. Ранее говорилось о графах Коллатца, которые представляют собой паутину чисел, связанных между собой некоторыми отрезками. И всё. В статье делается упор на построение веток дерева, которые сразу решают проблему. Ведь ветки дерева представляют собой определённую последовательность натуральных чисел. А это позволило продвинуться в доказательстве гипотезы. Кроме того, ранее говорилось, что для почти всех натуральных чисел существует время остановки (число в последовательности меньше начального числа). И всё. Я обнаружил закономерность появления одинакового времени остановки (количество шагов) для малых натуральных чисел через определённое количество чисел. А раз есть такая закономерность для малых чисел, значит, она есть и для больших чисел (эвристика). Значит, нет чисел, кроме 1, для которых можно ввести определение минимального числа, для которого, в свою очередь, неверна гипотеза. Извините за длинный ответ.



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

23.07.2021, 15:53 Усов Геннадий Григорьевич
Отзыв: Сделал статью немного покороче


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


 
 

Вверх