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

Доказательство отсутствия эффекта цикличности в последовательностях Коллатца

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

к.т.н.

МГУ, 1972

пенсионер

УДК 511

Введение

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

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

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

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

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

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

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

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

В этом случае возможны два варианта:

- последовательность Коллатца всё время увеличивается до бесконечности;

- последовательность Коллатца имеет циклическую бесконечную последовательность.

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

В частности, Рихо Террас доказал [2], что почти каждое натуральное число имеет конечное время остановки при построении последовательности Коллатца . Другими словами, в почти каждой последовательности Коллатца для любого числа последовательности найдётся в этой последовательности число, которое будет меньше этого числа. И так до тех пор, пока в этой последовательности не появится число 1.

В 2019 году Теренс Тао улучшил этот результат, показав, используя логарифмическую плотность, что почти все (в смысле логарифмической плотности) орбиты Коллатца нисходят ниже любой заданной функции начальной точки, при условии, что эта функция расходится к бесконечности, как бы медленно это ни происходило [2].

При этом Теренс Тао применил термин «орбита» для обозначения последовательностей Коллатца. Автор решил остановиться на ранее существовавшем термине – «последовательность».

 

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

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

 

Цели и задачи

В данной статье рассматривается доказательство отсутствия эффекта цикличности в гипотезе Коллатца.

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

    y(i),   0  <= i <= n,

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

Тогда задача определения эффекта цикличности заключается в сравнении первоначального числа последовательности y(0)  с числом последовательности y(i), которое получается после i-го этапа вычислений, то есть:

    y(0) = y(i).

Что и является целью статьи.

Можно за эффект цикличности принять числа 1, 4, 2, 1, 4, 2, … Однако здесь нет эффекта цикличности для гипотезы Коллатца, поскольку процесс определения членов последовательности Коллатца заканчивается после определения числа 1.

 

Задача 1. Новое представление начального числа y(0) и определение этапов вычислений в построении чисел последовательности Коллатца.

Пусть имеется нечётное число y(0), для которого необходимо построить последовательность Коллатца.

Представим начальное число y(0) последовательности Коллаца в следующем виде:

     `y(0)=(y(0)+1)-1` .                                                                                    (1)

Как известно, числа последовательности Коллатца, где число y(0)  является начальным числом, определяются следующими этапами вычислений:

- одни этапы вычислений включают в себя последовательные вычисления вида:

     `y(i+1)=(y(i)*3+1)/2=((y(i)+1)*3-3+1)/2=(y(i)+1)*3/2-1` ,                           (2)

где y(i) – нечётное число,

- другие этапы вычислений включают в себя последовательные вычисления вида:

     `y(i+1)=(y(i))/2` ,                                                                                        (3)

где y(i) – чётное число.

Этап вычислений с формулой (2) действует до тех пор, пока не получится чётное число y(i+1).

Этап вычислений с формулой (3) действует до тех пор, пока не получится нечётное число y(i+1).

 

Задача 2. Формулы определения чисел последовательности Коллатца для различных этапов вычислений.

Поскольку y(0) – нечётное число, то на этапе 1 вычислений определения чисел последовательности Коллатца будет применяться формула (2), а именно:

     `y(1)=(y(0)+1)*3/2-1`                                                                                               (4)  

Поскольку этап 1 вычислений с формулой (2) продолжается до тех пор, пока не получится чётное число, то для числа y(1) применяется n1 раз (n1 >= 1) формула (2). Тогда из (4) получаем:

     `y(1)=(y(0)+1)*3^(n1)/2^(n1)-1=((y(0)+1)*3^(n1)-2^(n1))/2^(n1)` .                              (5)

Этап 1 вычислений заканчивается чётным числом y(1).  

Если y(1) – чётное число, то начинается этап 2 вычислений, и здесь применяется формула (3).

Поскольку этап 2 с формулой (3) продолжается до тех пор, пока не получится нечётное число, то для числа y(2) применяется несколько раз формула (3). Пусть таких применений формулы (3) будет m1 >= 1. Тогда из (5) получаем:

     `y(2)=(y(1))/2^(m1)=((y(0)+1)*3^(n1)-2^(n1))/(2^(n1)*2^(m1))` .                                           (6)

Поскольку y(2) – нечётное число, то на этапе 3 вычислений для числа y(3) применяется формула формулу (5):

     `y(3)=((y(2)+1)*3^(n2)-2^(n2))/2^(n2)` ,

где n2 >= 1– количество операций вида (2) на этапе 3 вычислений.

Подставляя y(2) из (6), получаем:  

     `y(3)=((((y(0)+1)*3^(n1)-2^(n1))/(2^(n1)*2^(m1))+1)*3^(n2)-2^(n2))/2^(n2)` ,

или:

     `y(3)=((((y(0)+1)*3^(n1)*3^(n2)-2^(n1)*3^(n2))/(2^(n1)*2^(m1))+3^(n2))-2^(n2))/2^(n2)` ,

или:

     `y(3)=((y(0)+1)*3^(n1)*3^(n2)-2^(n1)*3^(n2)+3^(n2)*2^(n1)*2^(m1)-2^(n2)*2^(n1)*2^(m1))/(2^(n2)*2^(n1)*2^(m1))` .

Обозначим:

     `w2=3^(n2)-3^(n2)*2^(m1)+2^(n2)*2^(m1)` .                                                                  (6а)

Здесь w2 – нечётное число из-за первого слагаемого.

Тогда получаем:

     `y(3)=((y(0)+1)*3^(n1)*3^(n2)-2^(n1)*w2)/(2^(n2)*2^(n1)*2^(m1))` .                                 (7)

Этап 3 вычислений заканчивается чётным числом y(3).  

Поэтому на этапе 4 вычислений для числа y(3) применяется формула (3), при этом m2 >= 1:

   `y(4)=(y(3))/2^(m2)=((y(0)+1)*3^(n1)*3^(n2)-2^(n1)*w2)/(2^(n2)*2^(n1)*2^(m1)*2^(m2))` ,    (8)

где m2 >= 1- количество операций вида (3) на этапе 4 вычислений.   

В результате получается нечётное число y(4).    

Поскольку y(4) – нечётное число, то на этапе 5 вычислений применяется формула (5):

     `y(5)=((y(4)+1)*3^(n3)-2^(n3))/2^(n3)` ,

где n3 >= 1 – количество операций вида (2) на этапе 5 вычислений.

Подставляя y(4) из (8), получаем:  

     `y(5)=((((y(0)+1)*3^(n1)*3^(n2)-2^(n1)*w2)/(2^(n2)*2^(n1)*2^(m1)*2^(m2))+1)*3^(n3)-2^(n3))/2^(n3)` ,

или:

     `y(5)=((((y(0)+1)*3^(n1)*3^(n2)*3^(n3)-2^(n1)*w2*3^(n3))+3^(n3)* 2^(n2)*2^(n1)*2^(m1)*2^(m2))-2^(n3)*2^(n2)*2^(n1)*2^(m1)*2^(m2))/( (2^(n2)*2^(n1)*2^(m1)*2^(m2)*2^(n3))` .

Обозначим:

       .             (8а)

Здесь w3 – нечётное число из-за первого слагаемого.

Тогда получаем:

     `y(5)=((y(0)+1)*3^(n1)*3^(n2)*3^(n3)-2^(n1)*w3)/(2^(n2)*2^(n1)*2^(m1)*2^(m2)*2^(n3))` .   (9)

Этап 5 вычислений заканчивается чётным числом y(5).  

Поэтому на этапе 6 вычислений для числа y(6) применяется формула (3):

   `y(6)=(y(5))/2^(m3)=((y(0)+1)*3^(n1)*3^(n2)*3^(n3)-2^(n1)*w3)/(2^(n2)*2^(n1)*2^(m1)*2^(m2)*2^(n3)*2^(m3))` .                   (10)

где m3 >= 1- количество операций вида (3) на этапе 6 вычислений.   

В результате получается нечётное число y(6).    

В работе [3] был определён ориентированный граф гипотезы Коллатца.

Тогда можно сказать, что:

- n1 чисел y(1), получаемых из уравнения (5), представляют собой часть чисел на ветви 1,

- m1 чисел y(2), получаемых из уравнения (7), представляют собой часть чисел на стволе 1,

- n2 чисел y(3), получаемых из уравнения (9), представляют собой часть чисел на ветви 2,

- m2 чисел y(4), получаемых из уравнения (10), представляют собой часть чисел на стволе 2.

- n3 чисел y(5), получаемых из уравнения (11), представляют собой часть чисел на ветви 3,

- m3 чисел y(6), получаемых из уравнения (12), представляют собой часть чисел на стволе 3.

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

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

 

Задача 3. Немного о К-циклах и группах этапов при определении последовательности Коллатца.

В работе [2] было представлено определение K – цикла:

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

Однако, при доказательстве отсутствия эффекта цикличности в последовательностях Коллатца данное название лучше заменить на другое название: группа этапов вычислений.

При построении последовательности Коллатца этапы вычислений поочерёдно меняются: сначала выполняется этап определения чисел на ветви ориентированного графа (нечётные числа), потом выполняется этап определения чисел на стволе ориентированного графа (чётные числа).

Если номер этапа вычислений нечётный, то это определение чисел последовательности Коллатца на очередной ветви графа. Если номер этапа вычислений чётный, то это определение чисел последовательности Коллатца на очередном стволе графа.

Можно одним номером обозначить группу этапов вычислений.

Например: имеется группа этапов 3, в которую входят этап 5 (ветвь 3) и этап 6 (ствол 3).

И для группы этапов 3 имеем следующие положительные показатели степеней:

     n1, n2, n3,         и        m1, m2, m3.

 

Задача 4. Построение обобщённой формулы этапов вычислений чисел последовательности Коллатца.

Определим группу этапов вычислений V.

Тогда для группы этапов V получаем формулы для определения чисел:

- на стволе V:

     `y(2*v)=((y(0)+1)*A-2^(n1)*w(v))/(B*C)` ,                                        (11)

где:

     `A=prod_(i=1)^v3^(ni)` ,

     `B=prod_(i=1)^v2^(ni)` ,

     `C=prod_(i=1)^v2^(mi)` ,

     w(v) – нечётное число из-за первого слагаемого.

 - на ветви V:

     `y(2*v-1)=y(2*v)*2^(m(v))` .                                                          (12)

Для группы этапов V имеем следующие положительные показатели степеней:

     n1, n2, n3, … , nv,         и        m1, m2, m3, … , mv.

 

Задача 5. Допущение о наличии циклической последовательности.                    

Проверка эффекта цикличности заключается в сравнении начального числа y(0) с числом последовательности y_i  на предмет их равенства:

    y(0) = y(i) .

Удобнее проверять цикличность при сравнении начального числа y(0) с числами на разных ветках, то есть на разных этапах вычислений при построении последовательности Коллатца.

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

Если на некоторой ветке есть число, которое находится в циклической последовательности, то это означает, что все числа на этой ветке находятся в циклической последовательности.

В циклической последовательности может находиться несколько веток.

Выберем из этих веток ту, где находится минимальное нечётное число, как на ветке, так и в циклической последовательности. И при построении циклической последовательности обязательно придём к этому числу единственным способом: по стволу, то есть в результате выполнения этапа 2*v.

При этом выбранное минимальное число не должно делиться на число 3.

Назовём это число как y(0), и это число будет начальным числом произвольной последовательности Коллатца.

 

Задача 6. Сравнение чисел y(0) и y(i) на разных этапах вычислений при построении последовательности Коллатца.           

         

Задача 6а. Проверка на цикличность (этап 2).

Для начала проверяется эффект цикличности на этапе 2 вычислений (7) (группа этапов 1).

Допустим, что есть равенство:

     `y(0)=(y(0)+1)*(3^(n1))/(2^(n1)*2^(m1))-1/(2^(m1))` ,

или:

     `y(0)*(2^(n1)*2^(m1))=(y(0)+1)*(3^(n1))-(2^(n1))` ,

или:

     `y(0)*(2^(n1)*2^(m1)-3^(n1))=3^(n1)-2^(n1)` .                                                       (15)

Для выполнения условия (15) необходимо выполнение следующего условия:

     `0<(2^(n1)*2^(m1)-3^(n1))<(3^(n1)-2^(n1))` .                                                         (15а)

Для выполнения условия (15а) необходимо, чтобы количество цифр в двоичном счислении числа `(2^(n1)*2^(m1))` было на 1 больше, чем количество цифр в двоичном счислении числа `3^(n1)` .

У числа `(2^(n1)*2^(m1))` в двоичном счислении будет (n1+m1+1) цифр.

Тогда у числа `3^(n1)` в двоичном счислении будет (n1+m1) цифр.

Далее, чем больше у числа `3^(n1)` будет количество цифр 1, повторяющихся в старших разрядах двоичного счисления, тем будет меньше число `(2^(n1)*2^(m1)-3^(n1))` .

Определим, что количество цифр 1, повторяющихся в старших разрядах двоичного счисления, будет равно числу p.

У числа `3^(n1)` в двоичном счислении почти одинаковое количество цифр 1 и количество цифр 0.

Поэтому, если даже все цифры 1 «сгруппировались» в верхних разрядах двоичного счисления числа `3^(n1)` (чего не может быть), то число p будет равно:

     `p = (n1+m1)/2` .                                                                                                   (15б)

Тогда число `(2^(n1)*2^(m1)- 3^(n1))` в двоичном счислении будет иметь `(n1+m1)/2` цифр.

 

Теперь запишем условие (15) в следующем виде:

     `(y(0)+1)*(2^(n1)*2^(m1)-3^(n1))=2^(n1)*(2^(m1)-1)` .                                         (15в)

Из условия (15в) видно, что число (y(0)+1) делится на число `2^(n1)` , согласно (5).

Тогда число `(2^(m1)-1)` должно делиться на число `(2^(n1)*2^(m1)-3^(n1))` нацело.

У числа `(2^(m1)-1)` в двоичном счислении m1 цифр.

У числа `(2^(n1)*2^(m1)-3^(n1))` в двоичном счислении, согласно (15б), `(n1+m1)/2` цифр.

Числа n1, начиная с n1=3, всегда больше числа m1. Например:

     `2^3*2^2gt3^3` и `2^6*2^4gt3^6` .

Причём, чем больше будет число n1, тем больше будет разница между числом n1 и числом m1.

Тогда, у числа `(2^(n1)*2^(m1)-3^(n1))` будет больше цифр в двоичном счислении, чем у числа `(2^(m1)-1)` в двоичном счислении.

Следовательно, число `(2^(m1)-1)` не может делиться на числа `(2^(n1)*2^(m1)-3^(n1))` .

Значит, условия (15в) и (15) не могут быть выполнены в целых числах, за исключением случая, когда n1=m1:

     `2^2*2^2gt3^2` .

Получается, что на этапе 2 невозможен эффект цикличности в последовательностях Коллатца при начальном числе, большем числа 1. 

 

Задача 6б. Проверка на цикличность (этап 4).

Теперь проверяется эффект цикличности на этапе 4 вычислений (7) (группа этапов 2).  

Допустим, что есть равенство:

     `y(0)=((y(0)+1)*3^(n1)*3^(n2)-2^(n1)*w2)/(2^(n2)*2^(n1)*2^(m1)*2^(m2))` ,     

или:   

     `y(0)*(2^(n2)*2^(n1)*2^(m1)*2^(m2)-3^(n1)*3^(n2))=3^(n1)*3^(n2)-2^(n1)*w2` ,         (18)  

где w2 из (6а).

Теперь изменим уравнение (18) следующим образом:

     `y(0)*(2^(n1)*p-q)=q` ,                                                                                         (19)

где:

     `p=2^(n2)*2^(m1)*2^(m2)-w2` ,

     `q=3^(n1)*3^(n2)-2^(n1)*w2` .

При этом числа p и q – нечётные, так как w2 – нечётное число.

В результате получаем уравнение (19), аналогичное уравнению (16) в задаче 5а.

Но уравнение (16) не решается в целых числах.

Следовательно, уравнения (19), (18а) и (18) не решаемы в целых числах.

Получается, что на этапе 4 невозможен эффект цикличности в последовательностях Коллатца. 

Замечание:  невозможен вариант 2 из задачи 5а, так как число (n1+n2) всегда больше числа 2, за исключением случая «повтора операции» - цикличность для начального числа 1.

 

Задача 6в. Проверка на цикличность (этап 6).

Теперь проверим цикличность на этапе 6 вычислений (12) (группа этапов 3).  

Допустим, что есть равенство:

`y(0)=((y(0)+1)*3^(n1)*3^(n2)*3^(n3)-2^(n1)*w3)/(2^(n2)*2^(n1)*2^(m1)*2^(m2)*2^(n3)*2^(m3))` , 

или:

`y(0)*(2^(n2)*2^(n1)*2^(m1)*2^(m2)*2^(n3)*2^(m3)-3^(n1)*3^(n2)*3^(n3))=3^(n1)*3^(n2)*3^(n3)-2^(n1)*w3` ,    ( 20)

где w3 из (8а).

Теперь изменим уравнение (20) следующим образом:

     `y(0)*(2^(n1)*p-q)=q` ,                                                                         (21)

где:

     `p=2^(n2)*2^(m1)*2^(m2)*2^(n3)*2^(m3)-w3` ,

     `q=3^(n1)*3^(n2)*3^(n3)-2^(n1)*w3` .

При этом числа p и q – нечётные, так как w3 – нечётное число.

В результате получаем уравнение (21), аналогичное уравнению (16) в задаче 5а.

Но уравнение (16) не решается в целых числах.

Следовательно, уравнения (21), (20а) и (20) не решаемы в целых числах.

Получается, что на этапе 6 невозможен эффект цикличности в последовательностях Коллатца. 

Замечание:  невозможен вариант 2 из задачи 5а, так как число (n1+n2+n3) всегда больше числа 2, за исключением случая «повтора операций» - цикличность для начального числа 1.

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

 

Задача 6г. Проверка на цикличность (этап 2*V).

Теперь проверим цикличность на этапе 2*V вычислений (23) (группа этапов V). 

Допустим, что есть равенство:

     `y(0)=((y(0)+1)*A-2^(n1)*w(v))/(B*C)` ,

или:   

     `y(0)*(B*C-A)=A-2^(n1)*w(v))` ,

или:   

     `y(0)*(B*C-2^(n1)*w(v)+2^(n1)*w(v))-A)=A-2^(n1)*w(v)` .                  (24)

Теперь изменим уравнение (24) следующим образом:

     `y(0)*(2^(n1)*p-q)=q` ,                                                                             (25)

где:

     `q=A-2^(n1)*w(v)` ,

     `p=(B*C)/2^(n1)-w(v)` .

При этом числа p и q – нечётные.

В результате получаем уравнение (25), аналогичное уравнению (16) в задаче 5а.

Но уравнение (16) не решается в целых числах.

Следовательно, уравнения (25), (24a) и (24) не решаемы в целых числах.

Замечание:  невозможен вариант 2 из задачи 5а, так как число (А) всегда больше числа 2, за исключением случая «повтора операций» - цикличность для начального числа 1.

Получается, что на произвольном этапе (2*V) вычислений чисел последовательностей Коллатца невозможен эффект цикличности, за исключением начального числа 1.

 

Таким образом, в последовательностях Коллатца невозможен эффект цикличности.

 

Выводы.

Определено новое представление начального числа последовательности Коллатца.

Определено понятие этапов при определении чисел последовательности Коллатца.

Доказано отсутствие эффекта цикличности в последовательностях Коллатца.

1. Открытые математические проблемы. [Электронный ресурс] // ru.wikipedia.org. URL: https://ru.wikipedia.org/wiki/Открытые_ математические_проблемы (дата обращения 10.05.2025)
2. Гипотеза Коллатца. [Электронный ресурс] // ru.wikipedia.org. URL: https://ru.wikipedia.org/wiki/Гипотеза_Коллатца (дата обращения 10.05.2025).
3. Усов Г. Г. Построение ориентированного графа Коллатца (гипотеза Коллатца). [Электронный ресурс] // SCI-ARTICLE.RU. 2024. URL: https://sci-article.ru/stat.php?i=1729763700 (дата обращения: 28.10.2024).

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

23.05.2025, 17:23 Цорин Борис Иосифович Отзыв: Доказательство снова не получилось, хотя на этот раз ошибки спрятаны получше. {1} При решении уравнения (17в) не учтено, что оно может решаться по Варианту 2; например, уравнение (16) имеет решение y(0)=7, n1=1, p=21, q=35 Естественно, мой пример решения (16) не учитывает выражения p и q через степени двойки и тройки, так как я не пытаюсь привести контрпример к гипотезе Коллатца; но в статье этот случай не разобран - значит, отсутствие циклов даже для двух этапов не доказано. {2} При решении уравнения (25) утверждается, что уравнение (16) не имеет решений, хотя у него решения были; хотя именно для заданных для уравнения 16 выражений для p и q в статье нашлось только решение из единиц, но для других нечетных значений p и q решений может быть куда больше. {3} Также не учтено, что в уравнении (25) p и q могут быть отрицательными, а для уравнения (16) отрицательные значения не рассматривались.

26.05.2025, 7:53 Цорин Борис Иосифович Отзыв: {1} "У Вас ошибка... Я считаю, что выражения (2^n1 * p - q) и q имеют отдельные разные делители" - скорее опечатка. y(0)=5, остальное - как было написано. Так что зря считаете. {2} "Согласен, что надо добавить решение 1, 4, 2, 1, 4, 2, … Других решений не может быть" - Вы сами нашли бесконечное множество решений 2^(n1)*p-q=1. Если исключить из решения утверждения p=2^(m1)-1, q=3^(n1)-2^(n1), которые уже не имеют отношения к уравнению (25), то откуда ж Вы возьмете 1, 4 и 2?

14.06.2025, 6:33 Усов Геннадий Григорьевич Отзыв: Борис Иосифович! Я поменял задачу 6а. Если там ошибок не будет, то можно продолжить применение данного метода на другие задачи в статье.

15.06.2025, 9:09 Цорин Борис Иосифович Отзыв: "У числа 3^(n1) в двоичном счислении почти одинаковое количество цифр 1 и количество цифр 0" - докажите. Только без своего любимого "я перебрал много и все время было так".

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