2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В раздел Пургаторий будут перемещены спорные темы (преимущественно псевдонаучного характера), относительно которых администрация приняла решение о нецелесообразности продолжения дискуссии.
Причинами такого решения могут быть, в частности: безграмотность, бессодержательность или псевдонаучный характер темы, нарушение автором принципов ведения дискуссии, принятых на форуме.
Права на добавление сообщений имеют только Модераторы и Заслуженные участники форума.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: Гипотеза Коллатца. Доказательство
Сообщение19.03.2023, 16:04 
Заслуженный участник
Аватара пользователя


27/05/11
873
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:

 Профиль  
                  
 
 Re: Гипотеза Коллатца. Доказательство
Сообщение19.03.2023, 17:26 
Заслуженный участник


31/12/05
1516
Martynov_M в сообщении #1586005 писал(а):
Единица - прародитель всех веток. И поэтому, развернув любую ветку в обратном направлении, мы возвращаемся к единице.
Замечательно. Вы построили бесконечное дерево и доказали, что все нечетные числа, попавшие в него, спускаются к 1. Остается доказать, что в него попали все нечетные числа. А то вдруг это дерево проходит мимо какого-то цикла? Извивается, шевелит листочками, но никак не дотянется до него…

 Профиль  
                  
 
 Re: Гипотеза Коллатца. Доказательство
Сообщение20.03.2023, 13:12 
Аватара пользователя


01/11/14
1894
Principality of Galilee
Gagarin1968 в сообщении #1586007 писал(а):
Кажется, есть такое число: $2^{81}-1$.
Прошу прощения, что ввёл в заблуждение. Просто в памяти отпечаталась именно эта степень двойки. Попробую уточнить.

 Профиль  
                  
 
 Re: Гипотеза Коллатца. Доказательство
Сообщение20.03.2023, 14:47 
Аватара пользователя


12/02/23
114
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},$ мы не сможем получить следующее нечётное?

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

 Профиль  
                  
 
 Всему цена - одиночество
Сообщение20.03.2023, 15:12 
Аватара пользователя


21/01/23

159
Запорожье
Martynov_M в сообщении #1586018 писал(а):
Если вы про первую (нулевую, исходную) итерацию, ветку (нечетных чисел) в гипотезе Коллатца, то она общеизвестна.
Мне не известна, можете дать ссылку? Хочется про нее почитать.

Цитата:
Это последовательность A002450: 1, 5, 21, 85, 341, 1365...
Она также содержит в себе 0.
Как это $0$? Все пути же ведут к $1$. Ладно допустим мы как-то дошли и до $0$ и как из $0$ дойти до $1$?

 Профиль  
                  
 
 Нуль
Сообщение20.03.2023, 15:21 
Аватара пользователя


12/02/23
114
Iosafat в сообщении #1586002 писал(а):
Сколько будет $\frac {1-1}{3}$?

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

 Профиль  
                  
 
 Re: Гипотеза Коллатца. Доказательство
Сообщение20.03.2023, 16:59 
Заслуженный участник


20/08/14
11668
Россия, Москва
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$), однако в них есть и другие циклы.

 Профиль  
                  
 
 Re: Гипотеза Коллатца. Доказательство
Сообщение20.03.2023, 17:31 
Заслуженный участник


31/12/05
1516
Martynov_M в сообщении #1586099 писал(а):
tolstopuz в сообщении #1586035 писал(а):
Замечательно. Вы построили бесконечное дерево
Отличное сравнение.
Да, так и есть. Рекурсия Коллатца – это дерево с бесконечными ветками. Единица – это прародитель всех веток.
Откуда вы знаете, что это дерево, а не кустарник? Может, есть число $X$, которое не встречается в дереве, построенном с $1$. Тогда над $X$ можно построить второй бесконечный куст.

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

 Профиль  
                  
 
 Re: Гипотеза Коллатца. Доказательство
Сообщение20.03.2023, 21:09 
Аватара пользователя


12/02/23
114
Martynov_M в сообщении #1586099 писал(а):
Есть ли такое нечетное число, подставив которое в $\frac {2n-1}{3}$ или $\frac {4n-1}{3}$ или $\frac {8n-1}{3}$ или $\frac {16n-1}{3},$ мы не сможем получить следующее нечётное?

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

 Профиль  
                  
 
 0 - чётный?
Сообщение21.03.2023, 12:58 
Аватара пользователя


21/01/23

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

 Профиль  
                  
 
 Re: Гипотеза Коллатца. Доказательство
Сообщение21.03.2023, 13:08 
Аватара пользователя


12/02/23
114
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$, с таким шагом рекурсии мы покрываем все нечетные числа.

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

 Профиль  
                  
 
 Re: Гипотеза Коллатца. Доказательство
Сообщение21.03.2023, 14:16 
Админ форума


02/02/19
2460
 i 
Martynov_M в сообщении #1586196 писал(а):
Такой шаг рекурсии, как показал Lek
Ник участника нужно воспроизводить точно (регистр букв важен) и выделять жирным шрифтом. Тогда участник увидит, что его упомянули. Чтобы точно воспроизвести ник, достаточно кликнуть на него.

 Профиль  
                  
 
 Re: Гипотеза Коллатца. Доказательство
Сообщение21.03.2023, 16:03 
Заслуженный участник
Аватара пользователя


27/05/11
873
Martynov_M в сообщении #1586196 писал(а):
Такой шаг рекурсии, как показал Lek, не подразумевает повторных чисел, циклов и зацикливания.

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

 Профиль  
                  
 
 Re: Гипотеза Коллатца. Доказательство
Сообщение21.03.2023, 18:30 
Заслуженный участник


31/12/05
1516
Martynov_M в сообщении #1586196 писал(а):
Лемма. Все нечетные числа между $n$ и $4n+1$ спускаются к единице.

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

 Профиль  
                  
 
 Re: Гипотеза Коллатца. Доказательство
Сообщение21.03.2023, 20:38 
Заслуженный участник


20/08/14
11668
Россия, Москва
Martynov_M в сообщении #1586196 писал(а):
Лемма. Все нечетные числа между $n$ и $4n+1$ спускаются к единице.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 83 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group