2014 dxdy logo

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

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


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


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



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


15/10/08
11569
Dmitriy40 в сообщении #1586232 писал(а):
при доказательстве леммы Вы используете её же саму? Оригинально-с!
Ну так, рекурсия же.

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


20/08/14
11112
Россия, Москва
Тогда не показано что после применения одного (или любого конечного числа) шага рекурсии происходит уменьшение исходного нечётного числа.

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


12/02/23
74
tolstopuz в сообщении #1586223 писал(а):
Я ничего не понял. Давайте возьмем для определенности $n=3$ и докажем описанным вами способом, что все нечетные числа между $n$ и $4n+1$ спускаются к единице.

$n=3$.
Применяем правило $4n+1$. Получаем интервал [3...13].

Число 3 спускается к единице, потому что оно получено рекурсивно из нижестоящего интервала. Мы предполагаем, что нижестоящей интервал от [1...5] уже доказан.
Число 13 это $4n+1$, такое число гарантированно спускается к единице, потому что оно цепляется за начало интервала, за число 3.
В интервале [3...13] остаются числа: 5, 7, 9, 11.

Обратим внимание, что мы уже внутри рекурсии и можем двигаться как вперед, так и назад.
Сделаем рекурсивный шаг назад из числа 3. Получаем число 5.
Сделаем рекурсивный шаг вперед из числа 13. Получаем 11, 7, 9.
Вот и всё, интервал покрыт.

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


31/12/05
1479
Martynov_M в сообщении #1586266 писал(а):
Сделаем рекурсивный шаг вперед из числа 13. Получаем 11, 7, 9.
Как именно получаем?

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


12/02/23
74
По правилу 1/3, через последовательное применение $\frac {2n-1}{3}$ и $\frac {4n-1}{3}$.
13 $\rightarrow$ 17 $\rightarrow$ 11 $\rightarrow$ 7 $\rightarrow$ 9.

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


20/08/14
11112
Россия, Москва
Martynov_M в сообщении #1586388 писал(а):
По правилу 1/3, через последовательное применение $\frac {2n-1}{3}$ и $\frac {4n-1}{3}$.
Для любого $n$:
1. Сколько раз надо применить $\frac{4n-1}{3}$ перед применением $\frac{2n-1}{3}$?
2. Как это количество зависит от $n$?
3. Почему это количество конечно для всех $n$?
4. В каком вообще порядке надо применять эти два правила (какая зависимость порядка применения от $n$)?
5. Куда делись правила $\frac{8n-1}{3}$ и $\frac{16n-1}{3}$ и ещё куча аналогичных со степенью двойки? Их что, применять не нужно никогда? Даже например для получения $21$ из $1$? Как тогда вообще получить $21$? Из какого доказанного ранее интервала и как именно?
6. Почему в результате получатся все нечётные числа в интервале $[n, 4n+1]$?
На все эти вопросы ответов так и нет.

PS. Я по прежнему не вижу никаких принципиальных отличий правил от других, $\frac{2n+1}{3}$ и $\frac{4n+1}{3}$. В чём оно? Ведь эти правила дают циклы не сходящиеся к $1$, почему тогда те правила не могут таковых дать, в чём принципиальное отличие?

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


31/12/05
1479
Martynov_M в сообщении #1586388 писал(а):
По правилу 1/3, через последовательное применение $\frac {2n-1}{3}$ и $\frac {4n-1}{3}$.
13 $\rightarrow$ 17 $\rightarrow$ 11 $\rightarrow$ 7 $\rightarrow$ 9.
Не торопитесь. Вы сейчас не занимаетесь свободным творчеством, а показываете на примере, как работает ваше доказательство из поста выше.

Вы получили число $17$, выходящее за интервал $[3, 13]$. Почему вы продолжаете рекурсию дальше? В доказательстве этого нет, там написано, что интервалы будут рассматриваться последовательно.

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


12/02/23
74
Dmitriy40 в сообщении #1586394 писал(а):
Для любого $n$:
1. Сколько раз надо применить $\frac{4n-1}{3}$ перед применением $\frac{2n-1}{3}$?
2. Как это количество зависит от $n$?

Ни мы, ни рекурсия, не знает сколько раз нужно применить $\frac{4n-1}{3}$ перед применением $\frac{2n-1}{3}$.
Но если такая необходимость есть, то можно ввести в математике новую функцию, например, по подобию функции Эйлера. Потому что применение $\frac{4n-1}{3}$ и $\frac{2n-1}{3}$ зависит только от $n$.

Dmitriy40 в сообщении #1586394 писал(а):
4. В каком вообще порядке надо применять эти два правила (какая зависимость порядка применения от $n$)?

Если $n \equiv 1 \pmod 3$, то применяем $\frac{4n-1}{3}$.
Если $n \equiv 2 \pmod 3$, то применяем $\frac{2n-1}{3}$.

Dmitriy40 в сообщении #1586394 писал(а):
3. Почему это количество конечно для всех $n$?

Хороший вопрос. Я задавался этим вопросом перед публикацией статьи. Мне тоже было интересно, есть ли такие числа, которые беспрерывно возрастают по правилу 1/3 ? Т.е. есть ли такие числа, которые не имеют хвоста рекурсии? Нет, таких чисел нет. Я не нашел.

Любая ветка рекурсии, любое применение $\frac{4n-1}{3}$ и $\frac{2n-1}{3}$ всегда заканчивается хвостом рекурсии $n \equiv 0 \pmod 3$.

Dmitriy40 в сообщении #1586394 писал(а):
5. Куда делись правила $\frac{8n-1}{3}$ и $\frac{16n-1}{3}$ и ещё куча аналогичных со степенью двойки? Их что, применять не нужно никогда?

Во-первых, не нужно. Во-вторых, $\frac{8n-1}{3}$ и $\frac{16n-1}{3}$ - это не правила. Это раздвоенные ветки числа $n$.

Если число $n$ связано с другим числом $x$ через правило $\frac{2n-1}{3}$, то число $n$ также будет связано с раздвоенной веткой $4x+1$:
$x = \frac{2n-1}{3}$, $y = \frac{8n-1}{3}$
$y = 4x+1$

И аналогично, если число $n$ связано с числом $x$ через правило $\frac{4n-1}{3}$, то число $n$ также будет связано с раздвоенной веткой $4x+1$:
$x = \frac{4n-1}{3}$, $y = \frac{16n-1}{3}$
$y = 4x+1$

Всё это было нужно нам в начале статьи, чтобы показать, что при спуске к единице мы можем заменить число вида $4x+1$ на его производное и спуск до 1 не изменится.
Посмотрите на рисунок. Он показывает, что степени двойки нам безразличны. Нас интересует только связь $4x+1$.

Изображение

В общем, забудьте о формулах $\frac{8n-1}{3}$ и $\frac{16n-1}{3}$. Мы уже выкинули все чётные числа из рекурсии и для нас теперь есть только одна истинная связь $4x+1$.

Dmitriy40 в сообщении #1586394 писал(а):
5. Как тогда вообще получить $21$? Из какого доказанного ранее интервала и как именно?

$n$=5, интервал [5...21].
Мы предполагаем, что нижестоящие интервалы [1...5], и [3...13] уже доказаны. Тогда числа 1, 3, 5, 7, 9, 11, 13 - не нуждаются в доказательстве.
Остается доказать 15, 17, 19.

Сделаем шаг вперед для числа 13, $n \equiv 1 \pmod 3$. Мы получаем 17.
Сгенерируем новую ветку $4n+1$ для 13. В этой ветке мы получаем 15.
Возвратимся к 7 и аналогично применим $4n+1$, мы получаем ветку, в которой есть 19.
Интервал [5...21] покрыт.

Но это самые простые интервалы в гипотезе Коллатца.
Далее нас ждем интервал [7...29], в котором есть магическое число 27. Чтобы до него добраться, нам придется познать "всю горечь" рекурсии и залезть в самые дебри вложенных друг в друга веток.

tolstopuz в сообщении #1586449 писал(а):
Вы получили число $17$, выходящее за интервал $[3, 13]$. Почему вы продолжаете рекурсию дальше? В доказательстве этого нет, там написано, что интервалы будут рассматриваться последовательно.

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

Dmitriy40 в сообщении #1586394 писал(а):
6. Почему в результате получатся все нечётные числа в интервале $[n, 4n+1]$?

Во-первых, я взял этот интервал интуитивно, потому что, например, для хвоста рекурсии $3$ есть только один способ продолжить рекурсию – это применить $[4n+1]$.
Во-вторых, что я еще могу сказать? Это рекурсия. Она беспощадна к нашему представлению о том, как можно выразить всё это формулой.
Как сказали нам отцы основатели Тьюринг, Пост, Чёрч, Клини: Не все математические задачи могут быть решены через формулы. И после этого они создали раздел математики алгоритмы, включающий в себя рекурсии.

Наш алгоритм перебирает все числа по mod(3). Почему? Я не знаю. Вопрос открыт.
Я выдвинул лемму об интервале $[n, 4n+1]$ т.к. мне она представляется самой интуитивно понятной для последующего доказательства.

Dmitriy40 в сообщении #1586394 писал(а):
PS. Я по прежнему не вижу никаких принципиальных отличий. Ведь другие правила дают циклы не сходящиеся к $1$. В чём принципиальное отличие?

Посмотрите на эту таблицу:

Изображение

Во втором столбце расписаны все шаги рекурсии, все возможные итерации, все возможные числа, которые могут быть получены рекурсией когда-либо при применении какого-либо правила к какому-либо числу на каком-либо шаге итерации.

Как показал Lek, такой шаг рекурсии не подразумевает повторов.
Какое вам еще нужно доказательство?

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


31/12/05
1479
Martynov_M в сообщении #1586468 писал(а):
Но мы можем рекурсивно спуститься на любую глубину уже известного нам числа (из любого другого предыдущего известного нам интервала)
Насколько я понимаю, вы пытаетесь доказать гипотезу Коллатца. Ее утверждение как раз и состоит в том, что рекурсивный спуск когда-нибудь приведет к $1$. Если же она вдруг неверна, то найдется число, для которого рекурсивный спуск никогда не дойдет до $1$. То есть вы для доказательства гипотезы Коллатца пользуетесь гипотезой Коллатца? Это называется порочным кругом.

Вы сами пишете про интервал $[7,29]$, в котором есть магическое число $27$. Как конкретно ваше доказательство доказывает, что оно спускается к $1$? Повторю: не рассуждение, которое вы сейчас придумаете специально для этого числа, а ваше вышеописанное доказательство, которое вы поясняете на конкретных числах.

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


12/02/23
74
Что конкретно вам нужно показать? Распишите по шагам, что вы хотите увидеть? Какие-то шаги? Какие-то ветки?
Иначе мы друг друга не поймем.

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


20/08/14
11112
Россия, Москва
Martynov_M в сообщении #1586468 писал(а):
Нет, таких чисел нет. Я не нашел.
Выделенное жирным - вообще не аргумент если он не проверен для произвольного $n$ (в виде конечного списка формул размером не более $O(n)$), а не для некоторых заданных значений в программе, сколько бы их ни было.

Martynov_M в сообщении #1586468 писал(а):
$n$=5, интервал [5...21].
Мы предполагаем, что нижестоящие интервалы [1...5], и [3...13] уже доказаны. Тогда числа 1, 3, 5, 7, 9, 11, 13 - не нуждаются в доказательстве.
Остается доказать 15, 17, 19.

Сделаем шаг вперед для числа 13, $n \equiv 1 \pmod 3$. Мы получаем 17.
Сгенерируем новую ветку $4n+1$ для 13. В этой ветке мы получаем 15.
Возвратимся к 7 и аналогично применим $4n+1$, мы получаем ветку, в которой есть 19.
Интервал [5...21] покрыт.
Не покрыт: число 21 так и не получено ни в одной из веток. А в этом и был вопрос!

Martynov_M в сообщении #1586468 писал(а):
Какое вам еще нужно доказательство?
5-я страница темы заканчивается, а ничего более известной простой переформулировки гипотезы Коллатца не видно: не спуск по ветвям к корню 1, а подъём из корня 1 по всем возможным ветвям. Что прямой ход гипотезы может не реализоваться (и правило $3n-1$ тому пример!), что обратный подъём, разницы-то никакой, дерево-то одинаково строится и как его обходить несущественно.
Фактически Вы пытаетесь доказать что из некоего интервала все нечётные числа приходят (причём не видно где доказательство что за конечное число итераций) в строго меньший интервал, путём развёртывания этого меньшего интервала обратно в большой обратным ходом гипотезы и утверждением что в итоге получаете все нечётные числа большого интервала.

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


31/12/05
1479
Martynov_M в сообщении #1586487 писал(а):
Что конкретно вам нужно показать? Распишите по шагам, что вы хотите увидеть? Какие-то шаги? Какие-то ветки?
Иначе мы друг друга не поймем.

Martynov_M в сообщении #1586196 писал(а):
Лемма. Все нечетные числа между $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$, с таким шагом рекурсии мы покрываем все нечетные числа.

Вот ваш текст. Для меня он большей частью не имеет смысла. Я попросил вас на примере продемонстрировать его для $n=3$, вы вышли за рамки первоначального текста и придумали новое рассуждение. Сделайте следующую попытку: $n=7$, особо обратив внимание на число $27$. Повторяю: вы не должны придумывать новых объяснений, вы должны продемонстрировать, как работает вышепроцитированное доказательство для $n=7$.

-- Пт мар 24, 2023 00:37:13 --

Сейчас ваше "доказательство" работает так: мы задаем конкретное $n$, зовем вас, и вы придумываете что-то для этого конкретного $n$. Это напоминает механического турка.

-- Пт мар 24, 2023 00:43:14 --

Dmitriy40 в сообщении #1586501 писал(а):
Не покрыт: число 21 так и не получено ни в одной из веток. А в этом и был вопрос!
Тут все хорошо. Автор в виде картинок излагает лемму, что при нечетном $n$ ветка числа $4n+1$ тривиально получается из ветки числа $n$.

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


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

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

tolstopuz в сообщении #1586505 писал(а):
Повторяю: вы не должны придумывать новых объяснений, вы должны продемонстрировать, как работает вышепроцитированное доказательство для $n=7$.

Для получения числа 27 вам нужно рекурсивно продолжить эту ветку:
1 $\rightarrow$ 5 $\rightarrow$ 3 $\rightarrow$ 13 $\rightarrow$ 53 $\rightarrow$ 35 $\rightarrow$ 23 $\rightarrow$ 15 $\rightarrow$ ... далее вы получите число 27.

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

-- 24.03.2023, 09:14 --

Dmitriy40 в сообщении #1586501 писал(а):
Число 21 так и не получено ни в одной из веток. А в этом и был вопрос!

Dmitriy40,
Число 21 это $4n+1$, такое число гарантированно спускается к единице, потому что оно цепляется за начало интервала, за число 5.

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


01/09/13
4318
Martynov_M в сообщении #1586525 писал(а):
Возможно, вы плохо понимаете, что такое рекурсия. Я такое допускаю, и готов вам помочь.

Я плохо понимаю. Приведите определение, пожалуйста.

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


10/03/16
3980
Aeroport
Geen
Рекурсия (перенаправлено с Рекурсия) -- см. Рекурсия

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

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



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

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


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

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