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

[Утундрий]

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

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

Ну так, рекурсия же.

[Dmitriy40]

Тогда не показано что после применения одного (или любого конечного числа) шага рекурсии происходит уменьшение исходного нечётного числа.

[Martynov_M]

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.
Вот и всё, интервал покрыт.

[tolstopuz]

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

Сделаем рекурсивный шаг вперед из числа 13. Получаем 11, 7, 9.

Как именно получаем?

[Martynov_M]

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

[Dmitriy40]

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$, почему тогда те правила не могут таковых дать, в чём принципиальное отличие?

[tolstopuz]

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]$. Почему вы продолжаете рекурсию дальше? В доказательстве этого нет, там написано, что интервалы будут рассматриваться последовательно.

[Martynov_M]

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, такой шаг рекурсии не подразумевает повторов.
Какое вам еще нужно доказательство?

[tolstopuz]

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

Но мы можем рекурсивно спуститься на любую глубину уже известного нам числа (из любого другого предыдущего известного нам интервала)

Насколько я понимаю, вы пытаетесь доказать гипотезу Коллатца. Ее утверждение как раз и состоит в том, что рекурсивный спуск когда-нибудь приведет к $1$. Если же она вдруг неверна, то найдется число, для которого рекурсивный спуск никогда не дойдет до $1$. То есть вы для доказательства гипотезы Коллатца пользуетесь гипотезой Коллатца? Это называется порочным кругом.

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

[Martynov_M]

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

[Dmitriy40]

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$ тому пример!), что обратный подъём, разницы-то никакой, дерево-то одинаково строится и как его обходить несущественно.
Фактически Вы пытаетесь доказать что из некоего интервала все нечётные числа приходят (причём не видно где доказательство что за конечное число итераций) в строго меньший интервал, путём развёртывания этого меньшего интервала обратно в большой обратным ходом гипотезы и утверждением что в итоге получаете все нечётные числа большого интервала.

[tolstopuz]

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$.

[Martynov_M]

Лемма. Все нечетные числа между $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.

[Geen]

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

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

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

[ozheredov]

Geen
Рекурсия (перенаправлено с Рекурсия) -- см. Рекурсия