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

[Dmitriy40]

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

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

Какое правило применять для $n \equiv 0 \pmod 3$?

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

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

Оп-па, а Ваш-то обход дерева вовсе не соответствует обратному обходу по гипотезе Коллатца! Потому что по ней 53 получается из 35 (или 141 или 565 или $(106\cdot4^k-1)/3, k=0\ldots\infty$), а совсем не из 13. Ровно как и 3 получается не из 13, а из 6 (и больших исключительно чётных).
Соответственно если взять доказанный интервал $[1,2]$ и попытаться доказать вашим методом следующий интервал $[3,13]$ моментально возникает вопрос как доказать $n=3$. Попытка применить к $n=3$ правило $4n+1$ (судя по процитированному куску где из 3 получается 13) приводит к уходу чисел на бесконечность $3, 13, 17, 11, 7, 9, 37, 49, 65, 43, 57, 229, 305, 203, 135, 541, 721, 961, 1281,\ldots$, при этом в последовательности нет ни одного доказанного числа. И эта последовательность отличается от процитированной вашей, где указан переход $13\to53$, хотя по правилу $n \equiv 1 \pmod 3$ должно быть $(4\cdot13-1)/3=17$. Т.е. Вы ещё и неправильно применяете свои же правила!

Martynov_M
Итак, два вопроса:
1. Какое правило применять при $n \equiv 0 \pmod 3$ для получения следующего $n$? $4n+1$ или какое-то другое?
2. Как по Вашим правилам доказывается $n=3$ при доказанном интервале $[1,2]$? Подробно напишите, по шагам, каждую итерацию, какое правило применяется, что по нему получается, в какой момент $n=3$ считается доказанным. Если с $n=3$ проблема из-за отсутствия доказанных интервалов, то можно взять $n=15$ с пусть даже как-то доказанным интервалом $[1,13]$ и рассмотреть его, для всех нечётных чисел $[3,13]$ каждое из них тоже добирается до 9 и потом одинаково уходит на бесконечность не проходя через 15. Т.е. по указанным правилам доказать $n=15$ не получается. Что делать?

[tolstopuz]

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

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

Сколько продолжать? Как именно продолжать на развилках? Слушать механического турка из ящика, который будет подсказывать?

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

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

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

[Martynov_M]

Dmitriy40
Спасибо вам очень большое, за ваши вопросы. Я знаю, насколько это тяжело разобраться в чужой работе. Респект вам.
И вам tolstopuz, тоже благодарность. Это моя вина, что статья получилась скомканная.
Это первая часть. Сейчас сосредоточился на написании второй части.
То, что написано в первой части - каждая строчка достоверна. Всё работает как часы. Проверено на миллионах последовательностях Коллатца. Проверено на компьютере.

Вот фрагмент кода. Его нужно запускать рекурсивно:

(Оффтоп)

Процедура ПрименитьПравила(n)
    
   Если (n % 3 = 1) Тогда
      ПервоеЧисло = (4*n - 1)/3;
      ВтороеЧисло = 4*n + 1;
   КонецЕсли;
   
   Если (n % 3 = 2) Тогда
      ПервоеЧисло = (2*n - 1)/3;
      ВтороеЧисло = 4*n + 1;
   КонецЕсли;

   Если (n % 3 = 0) Тогда
      ПервоеЧисло = 0; // хвост рекурсии
      ВтороеЧисло = 4*n + 1;
   КонецЕсли;
      
   ДобавитьНовоеЗначениеВТаблицу(ПервоеЧисло);
   ДобавитьНовоеЗначениеВТаблицу(ВтороеЧисло);
   
КонецПроцедуры

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

Для покрытия интервала от [1 ... 100] требуется 500 итераций.
Для покрытия интервала от [1 ... 1000] требуется 25000 итераций.
Для покрытия интервала от [1 ... 10000] требуется 1 млн. итераций.

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

Итак, два вопроса:
1. Какое правило применять при $n \equiv 0 \pmod 3$ для получения следующего $n$? $4n+1$ или какое-то другое?

$4n+1$. Мы всегда применяем $4n+1$ к любому числу.

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

2. Как по Вашим правилам доказывается $n=3$ при доказанном интервале $[1,2]$?

Постановка вопроса некорректна. Гипотеза Коллатца - это алгоритм. Мы его изучили, и пришли к выводу, что это простейшая рекурсия.
Рекурсия начинается с единицы. Мы можем её воспроизвести точь-в-точь, либо присмотреться к ней поближе, и выкинуть из нее чётные числа.
Осознав, что чётные числа нам не нужны (они фальшивые, ни на что не влияют), мы выкинули их из рекурсии. Мы сделали это для того, чтобы упростить доказательство.

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

2. В какой момент $n=3$ считается доказанным?

Число $n$ является доказанным, если оно рекурсивно получено из другого числа по правилам: $\frac{2n-1}{3} \quad \text{или} \quad \frac{4n-1}{3} \quad \text{или} \quad 4n+1.$
Эти правила - шаг рекурсии. Потому что они применяются рекурсией всегда, на любом шаге.

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

Напишите, по шагам, каждую итерацию, какое правило применяется?

Итерация №1.
Число 1. $n \equiv 1 \pmod 3$, применяем $\frac{4n-1}{3}, \quad \frac {4-1}{3} = 1$
Число 1. $4n+1=5.$

Итерация №2.
Число 5. $n \equiv 2 \pmod 3$, применяем $\frac{2n-1}{3}, \quad \frac {10-1}{3} = 3$
Число 5. $4n+1=21.$

Итерация №3.
Число 3. $n \equiv 0 \pmod 3$, хвост рекурсии.
Число 3. $4n+1=13.$

Итерация №4.
Число 13. $n \equiv 1 \pmod 3$, применяем $\frac{4n-1}{3}, \quad \frac {52-1}{3} = 17$
Число 13. $4n+1=53.$

Итерация №5.
Число 17. $n \equiv 2 \pmod 3$, применяем $\frac{2n-1}{3}, \quad \frac {34-1}{3} = 11$
Число 17. $4n+1=69.$

Итерация №6.
Число 11. $n \equiv 2 \pmod 3$, применяем $\frac{2n-1}{3}, \quad \frac {22-1}{3} = 7$
Число 11. $4n+1=45.$

Итерация №7.
Число 7. $n \equiv 1 \pmod 3$, применяем $\frac{4n-1}{3}, \quad \frac {28-1}{3} = 9$
Число 7. $4n+1=29.$

и т.д.

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

Сколько продолжать? Как именно продолжать на развилках? Слушать механического турка из ящика, который будет подсказывать?

Спасибо вам за теплые слова. :)
Продолжать рекурсивно. Это бесконечный процесс. Это рекурсия. Её нельзя остановить.
Коллатц предложил нам спуститься вниз по уже сформированной рекурсии. Но это слишком просто! Рекурсия проделала за нас всю работу. Мы лишь идем по её следам.

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

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

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

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

[tolstopuz]

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

Такая рекурсия покрывает любой интервал.

Очень самонадеянное утверждение. Вы показали, что такая рекурсия покрывает интервал $[1,10000]$. А как насчет интервала $[1,10^{30}]$?

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

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

Сколько продолжать? Как именно продолжать на развилках? Слушать механического турка из ящика, который будет подсказывать?

Спасибо вам за теплые слова. :)
Продолжать рекурсивно. Это бесконечный процесс. Это рекурсия. Её нельзя остановить.

Вы говорите, что, чтобы дойти до конкретного числа, скажем, $27$, надо продолжать бесконечно? Боюсь, тема скоро уедет в Пургаторий.

Кстати, вы не смотрели на проблему $3n+1$ на отрицательных числах? Там очень интересная ситуауция с числом $-5$, да и с $-17$ тоже. Продолжайте с $-1$ сколько хотите, но до этих чисел не дойдете.

[Martynov_M]

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

Очень самонадеянное утверждение. Вы показали, что такая рекурсия покрывает интервал $[1,10000]$. А как насчет интервала $[1,10^{30}]$?

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

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

Вы говорите, что, чтобы дойти до конкретного числа, скажем, $27$, надо продолжать бесконечно?

Мы сами вольны выбирать, что нам делать.
Если цель зайти в какую-то ветку, поэкспериментировать, то можно продолжать бесконечно.

Но зачем? Если цель проверить рекурсию, скажем, покрывает ли она интервал от [1 ... 1000], то можно ограничить рекурсию двумя способами:
- Мы запрещаем рекурсии подниматься выше числа 1000000.
- Мы сортируем рекурсию на каждом шаге итерации, и заходим только в наименьшие ветви.

[tolstopuz]

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

Если цель проверить рекурсию, скажем, покрывает ли она интервал от [1 ... 1000], то можно ограничить рекурсию двумя способами:
- Мы запрещаем рекурсии подниматься выше числа 1000000.

Опять без подсказки от механического турка не обошлось. А что турок скажет про интервал $[1,10^7]$? А про $[1,N]$? А докажет ли он свои утверждения или снова будет придумывать какие-то числа на ходу?

[Martynov_M]

Tolstopuz
Во-первых, я вам, не турок. Во-вторых, поищите себе другого собеседника. Я вам советую сделать это следующим образом:
Переходите по ссылке на arxiv.org
Выбирайте любую понравившуюся вам работу по гипотезе Коллатца, в том числе ваших коллег, с этого форума.
И начинайте дискуссию с автором.

Подсказка. В 99% случаев автор не отвечает на письма пользователей. Через 10 лет вам, скорее всего, надоест, если вы не мазохист. Но вы пробуйте.

Есть другой способ – помолчать.
И третий способ – помочь с доказательством.
Что вы выберете?

[Ende]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Пургаторий (М)»
Причина переноса: спустя 6 страниц спорные моменты доказательства так и не были прояснены. Топикстартер либо не понимает критики, либо не желает ее понимать.