Гипотеза Коллатца. Первый шаг к доказательству

[lek]

Martynov_M в сообщении #1586013 писал(а):

Число 2417851639229258349412351. Это обычное число. Для спуска к единице требуется всего 649 итераций.

Подтверждаю. Прикрепил короткую программу на Maple (528 итераций).

(Оффтоп)

> restart:
> k[n+1]:=(3*k[n]+1)/2^p;
>
> for j from 81 to 81 do
> k[0]:=2^j-1:
> a[0]:=k[0]:
> n:=0:
> for i from 1 to 10^4 do
> k[i]:=k[i-1]:
> d[i]:=k[i] mod 2:
> if d[i]=0 then k[i]:=k[i]/2 else k[i]:=3*k[i]+1 fi:
> if igcd(k[i],2)=1 and k[i]>1 then a[n+1]:=k[i]: n:=n+1 fi:
> od:
> print(seq(a[i],i=0..n));
> print('n'=(n+1)[j]):
> od:

[tolstopuz]

Martynov_M в сообщении #1586005 писал(а):

Единица - прародитель всех веток. И поэтому, развернув любую ветку в обратном направлении, мы возвращаемся к единице.

Замечательно. Вы построили бесконечное дерево и доказали, что все нечетные числа, попавшие в него, спускаются к 1. Остается доказать, что в него попали все нечетные числа. А то вдруг это дерево проходит мимо какого-то цикла? Извивается, шевелит листочками, но никак не дотянется до него…

[Gagarin1968]

Gagarin1968 в сообщении #1586007 писал(а):

Кажется, есть такое число: $2^{81}-1$.

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

[Martynov_M]

tolstopuz в сообщении #1586035 писал(а):

Замечательно. Вы построили бесконечное дерево

Отличное сравнение.
Да, так и есть. Рекурсия Коллатца – это дерево с бесконечными ветками. Единица – это прародитель всех веток.
Это хорошо видно на следующем рисунке:



Но мне не нравится этот рисунок.
Он в недостаточной степени отображает, в моем понимании, самого главного - шага рекурсии:

$$n \equiv 1 \pmod 3 \quad \text{или} \quad n \equiv 2 \pmod 3 \quad \text{или} \quad n = 4x + 1.$$

Но вот этот рисунок, он просто замечательный:



Первое нечётное число, которое рождает единица – это 5, правило $4n+1$.
21 – это следующее нечетное число, снова правило $4n+1$.

Число 5 – это $n \equiv 2 \pmod 3$. У нас появляется возможность продолжить эту ветку по правилу 1/3. Мы получаем число 3.
Число 3 - это $n \equiv 0 \pmod 3$, хвост рекурсии. Но мы можем уйти на ветку $4n+1$. Мы получаем число 13.
Число 13 – это $n \equiv 1 \pmod 3$. У нас появляется возможность продолжить эту ветку по правилу 1/3. Мы получаем 17, 11, 7, 9 (хвост рекурсии).

Возвратимся к 7 и применим правило $4n+1$, мы получаем: 29, 19…
Возвратимся к 13 и применим $4n+1$, мы получаем: 53, 35, 23, 15 (хвост рекурсии).
И т.д.

На что надо обратить внимание?
С одной стороны, чётные числа – это вспомогательные числа. Они выполняют лишь функцию связующих чисел.
Потому что, как мы помним, в формулу $\frac {n-1}{3}$, мы можем подставить только чётные числа.

Но, согласно шагу итерации, все нечетные числа в последовательностях Коллатца отделены друг от друга либо 2$n$, либо 4$n$, либо 8$n$, либо 16$n$.

Тут на всякий случай вспомним наши старые рисунки, которые это хорошо демонстрируют:



И этот рисунок:



Предположим, что именно такой шаг рекурсии ($2n$, $4n$, $8n$, $16n$) покрывает все нечетные числа.
Тогда доказательство гипотезы Коллатца сводится лишь к вопросу:

Есть ли такое нечетное число, подставив которое в $\frac {2n-1}{3}$ или $\frac {4n-1}{3}$ или $\frac {8n-1}{3}$ или $\frac {16n-1}{3},$ мы не сможем получить следующее нечётное?

Если такое число есть, это будет первый контрпример!
Если нет, это означает, что все нечетные числа связаны между собой шагом итерации, и пропустить что-либо в нашей рекурсии мы просто не можем (и таким образом гипотеза Коллатца доказана).

[Iosafat]

Martynov_M в сообщении #1586018 писал(а):

Если вы про первую (нулевую, исходную) итерацию, ветку (нечетных чисел) в гипотезе Коллатца, то она общеизвестна.

Мне не известна, можете дать ссылку? Хочется про нее почитать.

Цитата:

Это последовательность A002450: 1, 5, 21, 85, 341, 1365...
Она также содержит в себе 0.

Как это $0$? Все пути же ведут к $1$. Ладно допустим мы как-то дошли и до $0$ и как из $0$ дойти до $1$?

[Martynov_M]

Iosafat в сообщении #1586002 писал(а):

Сколько будет $\frac {1-1}{3}$?

Iosafat,
Так нельзя делать. Мы не можем подставить 1 в правило $\frac {n-1}{3}$.
Потому что 1 - это нечетное.
Вопрос с нулем отпадает. Его нет в последовательности Коллатца. И в нашей рекурсии его тоже нет.

[Dmitriy40]

Gagarin1968 в сообщении #1586093 писал(а):

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

Можете не уточнять: никакие числа вида $2^p-1$ при $p<5000$ не требуют более 67400 итераций для прихода в 1 (и разумеется они все туда приходят). Проверяется за пару минут.

Martynov_M
Когда наконец Вы приступите к доказательству что в построенном дереве окажутся гарантированно все нечётные числа без пропусков? Без этого вся тема имеет околонулевой смысл и от повторов одного и того же он не появится. Вам уже приводили в пример последовательность $5n+1$, где сходимость к 1 (и соответственно обратная рекурсия из 1) вовсе не гарантирует отсутствие пропуска некоторых нечётных чисел. Где Ваше обоснование что в $3n+1$ такого не может быть? Сходимости к 1 некоторых чисел (или получения некоторых их из 1 обратным ходом) недостаточно. Нужно доказательство именно про все нечётные.

-- 20.03.2023, 17:19 --

И даже в последовательности $3n-1$ существуют разные циклы (например $5,14,7,20,10,5$ или $17,25,37,55,41,61,91,17$ если смотреть только нечётные). Чем $3n+1$ от них любых так принципиально отличается что не даёт никаких других циклов кроме $1,4,2,1$? Сходимости к 1 совершенно очевидно недостаточно, она есть в обеих (и $5n+1$, и $3n-1$), однако в них есть и другие циклы.

[tolstopuz]

Martynov_M в сообщении #1586099 писал(а):

tolstopuz в сообщении #1586035 писал(а):

Замечательно. Вы построили бесконечное дерево

Отличное сравнение.
Да, так и есть. Рекурсия Коллатца – это дерево с бесконечными ветками. Единица – это прародитель всех веток.

Откуда вы знаете, что это дерево, а не кустарник? Может, есть число $X$, которое не встречается в дереве, построенном с $1$. Тогда над $X$ можно построить второй бесконечный куст.

Вы нигде не доказали, что это невозможно.

[Martynov_M]

Martynov_M в сообщении #1586099 писал(а):

Есть ли такое нечетное число, подставив которое в $\frac {2n-1}{3}$ или $\frac {4n-1}{3}$ или $\frac {8n-1}{3}$ или $\frac {16n-1}{3},$ мы не сможем получить следующее нечётное?

Мой косяк. Прошу прощения. :(
Для хвоста рекурсии $n \equiv 0 \pmod 3$, это утверждение, конечно, не работает.

[Iosafat]

Почему гипотеза Коллатца начинается с единицы? $0$ - чётный на $100\%$?

[Martynov_M]

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

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

К любому нечетному числу $n$, начиная с единицы, мы можем применить правило $4n+1$.

Лемма. Все нечетные числа между $n$ и $4n+1$ спускаются к единице.

Доказательство. С одной стороны, применяя "правило 1/3" к числу $n$, мы создаем ветку рекурсии, которая гарантированно спускается к единице.
С другой стороны к каждому числу из этой ветки мы обязаны снова применить $4n+1$, что снова заставит его спускаться к единице.
Таким образом, рекурсия перебирает все нечетные числа по mod(3):

$$n \equiv 2 \pmod 3 \quad \text{или} \quad n \equiv 1 \pmod 3 \quad \text{или} \quad n \equiv 0 \pmod 3, \quad \text{хвост рекурсии.}$$

Такой шаг рекурсии, как показал Lek, не подразумевает повторных чисел, циклов и зацикливания.
А значит, такой шаг рекурсии покрывает все нечетные числа, потому что бесконечные интервалы между $n$ и $4n+1$ * $4n+1$ * $4n+1$ * $4n+1...$ охватывают все нечетные числа.
Другими словами, начиная шагать с единицы по правилу $4n+1$, с таким шагом рекурсии мы покрываем все нечетные числа.

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

[Ende]

Martynov_M в сообщении #1586196 писал(а):

Такой шаг рекурсии, как показал Lek

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

[lek]

Martynov_M в сообщении #1586196 писал(а):

Такой шаг рекурсии, как показал Lek, не подразумевает повторных чисел, циклов и зацикливания.

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

[tolstopuz]

Martynov_M в сообщении #1586196 писал(а):

Лемма. Все нечетные числа между $n$ и $4n+1$ спускаются к единице.

Доказательство.

Я ничего в нем не понял. Давайте возьмем для определенности $n=3$ и докажем описанным вами способом, что все нечетные числа между $n$ и $4n+1$ спускаются к единице.

[Dmitriy40]

Martynov_M в сообщении #1586196 писал(а):

Лемма. Все нечетные числа между $n$ и $4n+1$ спускаются к единице.

Доказательство.
...
С другой стороны к каждому числу из этой ветки мы обязаны снова применить $4n+1$, что снова заставит его спускаться к единице.

Т.е. при доказательстве леммы Вы используете её же саму? Оригинально-с!