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

[Martynov_M]

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

Как это утверждение следует из вашей конструкции, непонятно.

Исходная рекурсия начинается с единицы. Эта рекурсия охватывает все нечетные числа. Почему? Потому что на каждой итерации мы запускаем всё новые и новые рекурсии (новые ветки), благодаря постоянному умножению на 2. И таким образом мы перебираем все возможные числа по правилу $\frac {n-1}{3}$. Развернув любую такую ветку в обратную сторону, мы как раз и получим гипотезу Коллатца $3n+1$.

Таким образом, $3n+1$ - это уже сформированная рекурсия от $\frac {n-1}{3}$. Это главная моя мысль. И поэтому спуск к 1 уже предрешен.

-- 18.03.2023, 17:52 --

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

То есть условие на шаг итерации написано для красоты, потому что мы не смотрим на него, а все равно продолжаем, в результате чего в настоящей (истинной) последовательности появляются не только числа, удовлетворяющие вышепроцитированному условию, но и прочие нечетные числа

Это не для красоты. :)

Это условие я специально проверял на всех последовательностях Коллатца от 1 до 1000000000. Именно по такому условию и шагает рекурсия.
Если мы, например, получили число $n \equiv 0 \pmod 3$, и оно не пошло дальше по условию $n = 4x + 1$, это хвост рекурсии. В таком случае уходим в другую ветку.

[tolstopuz]

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

Если мы, например, получили число $n \equiv 0 \pmod 3$, и оно не пошло дальше по условию $n = 4x + 1$, это хвост рекурсии. В таком случае уходим в другую ветку.

Что это за $n$ такое? Если $n$ нечетно, то $m=4n+1$ тоже нечетно, как оно может не пойти дальше по условию?

[Martynov_M]

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

В проблеме $5n+1$ существует цикл $13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13...$, то есть рекурсия, начинающаяся с единицы, никогда не дойдет до этих чисел. Где в вашем рассуждении доказательство, что аналогичного цикла не существует в проблеме $3n+1$?

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

[tolstopuz]

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

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

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

[Martynov_M]

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

Что это за $n$ такое? Если $n$ нечетно, то $m=4n+1$ тоже нечетно, как оно может не пойти дальше по условию?

Да, ветка $m=4n+1$ - это бесконечная ветка. Вы правы. Я заговорился. Не так сформулировал мысль. Извините :(.

В общем, как я делал проверку? Я взял нечетные числа от 1 до 1000000000 и посмотрел как они спускаются вниз к единице.
Все они рекурсивно спускаются вниз с шагом итерации:

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

Что я имел ввиду?
Если вы возьмете любое число $n \equiv 0 \pmod 3$, то это как бы "хвост рекурсии". Я не знаю как еще это назвать.
Но после такого числа, если вы шагаете из единицы и вдруг наткнулись на него, то вы уже никогда не получите в этой ветке $n \equiv 1 \pmod 3 \quad \text{или} \quad n \equiv 2 \pmod 3$. Вы получите только $n = 4x + 1.$

-- 18.03.2023, 18:38 --

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

Вы не доказали, что алгоритм, начатый с $1$, дает все нечетные числа без пропусков.

Полностью с вами согласен. Цель публикации была показать, что гипотеза Коллатца – это развернутая в обратном направлении рекурсия. И уже потом доказывать, почему так происходит, что эта рекурсия перебирает все нечетные числа, и они не встречаются на её пути заново.

[lek]

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

Цель публикации была показать, что гипотеза Коллатца – это развернутая в обратном направлении рекурсия.

Это известный и вполне оправданный подход (см. например, https://en.wikipedia.org/wiki/Collatz_conjecture -> Other formulations of the conjecture -> In reverse).

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

И уже потом доказывать, почему так происходит, что эта рекурсия перебирает все нечетные числа

Это утверждение равносильно гипотезе Коллатца. Для "почти всех" натуральных чисел оно следует из известной работы Терри Тао 2019 года.

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

... и они не встречаются на её пути заново

Это утверждение доказывается тривиально.

[tolstopuz]

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

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

Вы не доказали, что алгоритм, начатый с $1$, дает все нечетные числа без пропусков.

Полностью с вами согласен.

То есть тема и параграф 8 названы неправильно и их надо переименовать?

[Martynov_M]

Tolstopuz
Я понял, почему такая путаница произошла. По крайней мере, у меня, что мне тяжело вас понять. :(
Ветка $4n+1$ может цеплять разные числа. Это так.

Но когда я отвечал на ваши вопросы, я имел ввиду, что после того, как мы получили нечетное число вида $n \equiv 0 \pmod 3$ - оно уже не может идти дальше по условию $n \equiv 1 \pmod 3 \quad \text{или} \quad n \equiv 2 \pmod 3$.
Т.е. мы не можем дальше продолжать конкретно эту ветку (по правилу 1/3). Остается только условие $4n+1$.

Но переход в $4n+1$ - это уже новая ветка. Поэтому повторюсь, я имел ввиду, что как только мы получили число вида $n \equiv 0 \pmod 3$, то эта ветка в этом месте заканчивается, и начинается уже совсем другая ветка $4n+1$.

Т.е. когда я говорил про проверку на компьютере, я уточню, переходы $4n+1$ - я не проверял на mod (3). Мне это не нужно. И, вообще, это не нужно.
Все нечетные числа следуют друг за другом строго по правилу 1/3. Но как только они достигают $n \equiv 0 \pmod 3$ - в этом месте их ветка заканчивается. Начинается ответвление на $4n+1$, - вот это я как раз и проверял.
Tolstopuz, еще раз спасибо вам, что пытаетесь во всем разобраться. Респект вам. Задавайте вопросы. Другие участники, тоже подключайтесь.

-- 18.03.2023, 19:54 --

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

То есть тема и параграф 8 названы неправильно и их надо переименовать?

Да, можно переименовать: Доказательство. Шаг 1.

-- 18.03.2023, 20:05 --

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

(см. например, https://en.wikipedia.org/wiki/Collatz_conjecture -> Other formulations of the conjecture -> In reverse).

Но там нет упоминания о рекурсии, как о причине.

-- 18.03.2023, 20:11 --

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

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

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

Это утверждение доказывается тривиально.

Lek, можете доказать? :)

[Antoshka]

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

В общем, как я делал проверку? Я взял нечетные числа от 1 до 1000000000 и посмотрел как они спускаются вниз к единице.
Все они рекурсивно спускаются вниз с шагом итерации:

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

Что я имел ввиду?

Так вы взяли ограниченное количество чисел. Где гарантия, что если взять $10^{500}+1$, то они так же будут рекурсивно спускаться вниз? Вы же не можете перебрать вручную все числа

[Martynov_M]

Терминология
Давайте определимся, что под шагом рекурсии (шагом итерации):

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

мы подразумеваем два правила: 1/3 и $4x+1$.
Под термином "отдельная ветка", мы подразумеваем последовательность чисел следующих друг за другом по правилу 1/3.
Как только такая последовательность достигает $n \equiv 0 \pmod 3$, ветка заканчивается.
Переход числа в ветку $4x+1$ - это всегда новая ветка.

Под рекурсией $\frac {n-1}{3}$ мы будем подразумевать все возможные итерации с бесконечными вариациями и ответвлениями по правилу 1/3 и $4x+1$, а также всю их совокупность на любом шаге. В математике этот вид рекурсии называется возвратная, или рекурсия с пробегом.

Далее, мы соглашаемся, что гипотеза Коллатца $3n+1$ - это развернутая в обратном направлении рекурсия $\frac {n-1}{3}$.
Если да, то нам уже не нужно больше ничего доказывать. Почему? Потому что это рекурсия. Она начинается с единицы. Развернув ее в обратную сторону у нас нет другого варианта, как снова спуститься к 1.

Но мы спросим: А есть ли такое число, которое не входит в рекурсию $\frac {n-1}{3}$ ?
Предположим, что есть. Но тогда из этого следует, что его нельзя подставить в $3n+1$. Потому что $3n+1$ - это уже сформированная рекурсия от $\frac {n-1}{3}$.

Что я пытаюсь вам сказать? А вот, что! Коллатц предложил нам головоломку $3n+1$, не сказав, что мы уже, как зверь в клетке, вступили на поле рекурсии.
Вопрос Коллатца: Есть ли такое число, которое не рождено единицей?
Ответ: Нет.

Доказательство
Для любого нечетного числа, уже начиная с 1, мы можем применить правила 1/3 и $4x+1$.
Таким образом, нет такого числа, к которому мы не могли бы применить эти правила.
Развернув эти правила в обратную сторону, мы получим единицу.
Эти правила – часть рекурсии. Это означает, что любое нечетное число можно представить как рекурсию из других чисел.
Акцентирую! Всего один раз применив $3n+1$ и $n/2$ мы уже находимся в рекурсии. Ч.т.д.

[lek]

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

Но там нет упоминания о рекурсии, как о причине.

(?)

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

Lek, можете доказать?

В ваших обозначениях, пусть существуют такие $b\ne b'$, что $a\equiv a(m)_b=a(m')_{b'}\equiv a'$. Тогда $a=(2^pb-1)/3=(2^p'b'-1)/3=a'$ для некоторых натуральных $p$ и $p'$. Отсюда $2^pb=2^p'b'$ или $2^{p-p'}=b'/b$. Поскольку $b$ и $b'$ - нечетные, равенство справедливо только при $p=p'$. Следовательно $b=b'$. Получили противоречие. Таким образом, совпадающих ненулевых элементов во втором столбце вашей таблицы быть не должно.

[Martynov_M]

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

(?)

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

[lek]

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

[Martynov_M]

Тогда совсем всё просто. Объяснение гипотезы Коллатца звучит так:
- Коллатц попросил нас развернуть рекурсию в обратную сторону.
- Мы её развернули и получили 1. Почему? Потому что рекурсия началась с 1. Ч.т.д.

[Geen]

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

Мы её развернули и получили 1

Именно это и нужно доказать для всех нечётных.

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

Потому что рекурсия началась с 1.

Только если докажите, что покрыты все нечётные.