Циклы в гипотезе Коллатца

[Dmitriy40]

Всех приветствую!
В очередной раз наткнувшись на гипотезу Коллатца, вдруг подумалось что доказать отсутствие других циклов в ней кроме 4-2-1 совсем несложно и значит единственным вариантом её нарушения будет уход чисел в бесконечность.
Подскажите кто в курсе, это уже давно сделано и не стоит хвалиться своим велосипедом? Там идея всего лишь в том что $3^a = 2^b$ не выполняется ни при каких $a,b$ кроме тривиального $a=b=0$. Как-то слишком просто, давно кто-то должен был додуматься.

[lek]

Это открытая проблема:
https://library.lol/main/B4D2F20289CE57 ... EBA3D7E14F (Current Status - p.16)
https://en.wikipedia.org/wiki/Collatz_conjecture (Cycle length)

[Dmitriy40]

Хм, значит я где-то ошибаюсь ... Интересно где.

Пусть $w$ это минимальное число в цикле. Оно нечётное (чётное уменьшится следующей итерацией) и его можно представить как $4n+1$ или $4n+3$.
Первое из них тремя итерациями станет меньше исходного: $4n+1 \to 12n+4 \to 6n+2 \to 3n+1 < 4n+1$, значит единственно возможный вариант лишь $4n+3$, впрочем это утверждение для доказательства несущественно.
Рассмотрим как преобразуются числа $a,b$ с условиями $0<b<a, a>3, n>3$ из формулы $an+b$ при каждой итерации:
1. Итерация утроения и добавлением единицы: $a \to 3a, b \to 3b+1$, при этом сохраняется условие $3a>3b+1$. От добавления единицы $a$ увеличиться не может: $b<a \to 3b<3a \to 3b+1<3a+1<3(a+1)$.
2. Итерация деления пополам в случае чётного $a$: $a \to a/2, b \to b/2$, условие $a/2>b/2$ по прежнему сохраняется.
3. Итерация деления пополам в случае нечётного $a$ (и соответственно чётного $n$): $a \to a, b \to b/2$, условие $a>b/2$ по прежнему сохраняется.
Итого во всех итерациях исходное условие $a>b$ сохраняется. И в любых итерациях $a$ преобразуется или в $3a$ или в $a/2$ и никак иначе. Произвольная цепочка таких итераций в любом порядке преобразует $a$ как $a \to a\frac{3^x}{2^y}$ при некоторых ненулевых $x,y$. Чтобы число $4n+3$ (или $4n+1$, но оно по любому не подходит) входило в цикл надо чтобы выполнилось $4=4\frac{3^x}{2^y} \to 3^x=2^y$ для любых ненулевых $x,y$. Что невозможно. Выходит число $4n+3$ не может быть не только наименьшим числом в цикле, но и вообще в него входить на любой позиции. А значит циклов и нет (ну кроме тривиального, для которого не выполнены исходные условия).
Ну и в чём тут ошибка, кто подскажет?

[Rak so dna]

Dmitriy40 в сообщении #1617404 писал(а):

Рассмотрим как преобразуются числа $a,b$ с условиями $0<b<a, a>3, n>3$ из формулы $an+b$ при каждой итерации:
1. Итерация утроения и добавлением единицы: $a \to 3a, b \to 3b+1$, при этом сохраняется условие $3a>3b+1$. От добавления единицы $a$ увеличиться не может: $b<a \to 3b<3a \to 3b+1<3a+1<3(a+1)$.
2. Итерация деления пополам в случае чётного $a$: $a \to a/2, b \to b/2$, условие $a/2>b/2$ по прежнему сохраняется.
3. Итерация деления пополам в случае нечётного $a$ (и соответственно чётного $n$): $a \to a, b \to b/2$, условие $a>b/2$ по прежнему сохраняется.

1. В случае $3.$ уменьшается $n$, поэтому условие $a>b/2$ уже не важно.
2. Не рассмотрен случай деления пополам, когда $an$ и $b$ нечётные.

[mihaild]

Dmitriy40 в сообщении #1617404 писал(а):

Итерация деления пополам в случае нечётного $a$ (и соответственно чётного $n$)

А куда делся вариант $a, b, n$ все нечетные? И даже при четном $n$, условие $n > 3$ может нарушиться (хотя оно вроде и не используется).
Вообще, $a, b, n$ по числу определены сильно не единственно (любое $n$ от $4$ до $k / 4$ подойдет), что в точности понимается под преобразованием $a$ и $b$?

[lek]

Критическая ошибка в условии $4\frac{3^x}{2^y}=4$. Из равенства $a'n+b'=an+b$ не следует $a'=a$.

[Rak so dna]

lek в сообщении #1617417 писал(а):

Критическая ошибка в условии $4\frac{3^x}{2^y}=4$. Из равенства $a'n+b'=an+b$ не следует $a'=a$.

Ошибки нет. При больших $n$, малых $a$ и $0<b<a$ (как у ТС) представление единственно.

[Dmitriy40]

Спасибо, нечётность $a,n,b$ действительно всё портит. И это реально бывает уже для $16n+7 \to 27n+13$.

[lek]

Поясню свое замечание на примере обобщенной гипотезы Коллатца (https://en.wikipedia.org/wiki/Collatz_conjecture - Iterating on all integers), которая допускает нетривиальные циклы. Положим $a=-4$, $b=-1$, $n=1$ и $k=an+b$. Тогда пара преобразований вида $k\to k'=(3k+1)/2^p$, где $p$ - натуральное, а $k$ и $k'$ - нечетные целые, дает: $(a,b)=(-4,-1)\to (-6,-1)\to (-9/2,-1/2)=(a',b')$. Очевидно, что $a'\ne a$, но $a+b=a'+b'$.

[Dmitriy40]

Dmitriy40 в сообщении #1617429 писал(а):

нечётность $a,n,b$ действительно всё портит.

Даже нечётность $a$ на некоторой итерации уже всё ломает (быстро перестаёт выполняться инвариант $a>b$).

[MerkulovaLE]

Доказательство того, что функция Коллатца зацикливается только на единице:

Рассмотрим нечетные результаты функции Коллатца.

$f(2x+1) = \frac{(3x+2)}{2^n} $

Если на неком нечетном значении $a$ происходит зацикливание, то:

Рассмотрим $b$ и $c$: $b$ - значение непосредственно перед $a$ в цикле, $c$ - значение сразу после $a$.

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

$b,a,c, \ldots ,b,a,c,\ldots,b,a,c$

Функция от значения $c$ до значения $b$ проходит через значение $a$.

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

$b,a,c, \ldots,b,a,c \to b,a,c, \ldots ,a,c, \ldots ,b,a,c.$ И снова промежуток от $c$ до $b$

$2$ варианта избавления от этой раскрутки:

$b = c = a$ и $b = c $

$1$ вариант $f(y) = y$

$3x+1 = 2^n x$

$3x+1=2x $ нет целых положительных решений
$3x+1=4x$ ; $x=1$
$3x+1=8x$ и более - нет целых положительных решений

$2$ вариант$ f(f(y)) = y.$

$y $ или $f(y) = 4x+3$, так как в других случаях значение функции только уменьшается

$(4x+3)3+1 = 12x+10$

$\frac{(12x+10)}{2} = 6x+5$ - нечет

$(6x+5)3+1 = 18x+16$ - чет

$\frac{(18x+16)}{2} = 9x+8$

$9x+8 = 4x+3$ нет целых положительных решений

$4.5x+4 = 4x+3$ нет целых положительных решений

$2.25x+2 = 4x+3$ нет целых положительных решений

Дальше делить на $2$ смысла нет.

В итоге, единственный вариант цикла - единица.

[Dmitriy40]

Если я правильно понял, то Вы доказали что не может быть циклов длиной 1 ($f(y)=y$) и длиной 2 ($f(f(y))=y$). Ну ОК, пусть так (даже проверять не стал), а где доказательство что не может быть циклов длиннее, например длиной $10^{100500}$ итераций? Простите не буду выписывать столько раз взятие функции от аргумента, пальцы жалко. Без такого доказательства гипотеза Коллатца остаётся недоказанной.

[MerkulovaLE]

Доказательство, что в гипотезе Коллатца не может быть циклов из более, чем трех элементов:

В формуле Коллатца - рассмотрим только нечётные числа, их общая формула $\frac {3x+1}{2^k}$

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

Переход от третьего числа к первому в этом случае -
Третье число $\to$ первое число
и
Третье число $\to$ первое число $\to$ второе число$ \to$ третье число $\to$ первое число

Во втором цикле фигурирует второе число, которое не равно ни первому, ни третьему.
Но формула Коллатца не предусматривает ниоткуда взявшееся второе число.
И формула, обратная формуле Коллатца с элементом, не состоявшем в обратной формуле Коллатца от того же числа (третьего) не приводит к равному результату (первому).

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

Если более трёх чисел, то
Первое число $\to$ второе число $\to$ третье число $\to$ $\ldots$ $\to$ последнее число
И два варианта перехода от последнего числа к первому, доказывается аналогично случаю трёх чисел.

Случаи цикла из одного и двух чисел рассмотрены.

Тогда, для формулы $3x - 1 $только два варианта циклов:

$1\to2\to1$ и $5\to14\to7\to21\to5$

[mihaild]

MerkulovaLE в сообщении #1628014 писал(а):

нечётные числа, их общая формула $\frac {3x+1}{2^k}$

И как в таком виде представить число $9$?

MerkulovaLE в сообщении #1628014 писал(а):

Но формула Коллатца не предусматривает ниоткуда взявшееся второе число

Что такое "ниоткуда взявшееся число" и что такое "формула Коллатца предусматривает / не предусматривает" число?

[Dmitriy40]

MerkulovaLE в сообщении #1628014 писал(а):

Но формула Коллатца не предусматривает ниоткуда взявшееся второе число.

Обосновывайте.