Гипотеза Колатца

[grizzly]

Три А,да в сообщении #987938 писал(а):

Интересные свойства этих операторов:

Да, верно (и про свойства, и про то, что это интересно). Единственное, что в записи с использованием оператора $A$ обычно избегают действовать этим оператором на чётные числа -- пишут через степени двоек и троек в явном виде.

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

[Tot]

Известно ли диофантово уравнение на стартовое число, опровергающее гипотезу?

[Три А,да]

grizzly в сообщении #987977 писал(а):

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

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

А пока следующий шаг. Конечно не доказательство, но тем не менее:
Пусть $m$ делится на четыре, но не делится на восемь и удовлетворяет гипотезе Коллатца
Т.е.
$...B(A(B(B(m))))=1$
тогда, после перестановки операторов имеем
$...B(B(B(A(m)+3)))=1$
$(A(m)+3)=(3m+1+3)=(3(m+1)+1)=(A(m+1))$
Возвращаясь ко второму равенству получаем
$...B(B(B(A(m+1))))=1$
таким образом, если
$m\bmod4=0$
$m\bmod8\not=0$
$m$ удовлетворяет гипотезе Коллатца, то
$m+1$ также удовлетворяет гипотезе Коллатца

Подобное можно показать для всех $m=2^{2k}(2n+1)$, $k>1$, правда шаги уже будут другие.

[grizzly]

Три А,да

Я коротко опишу более аккуратную формулировку Вашего наблюдения и известные мне результаты в обобщении этого направления.

Действительно, легко заметить, что числа вида $8k+4$ и $8k+5$ ($k>0$) при применении итераций Коллатца достигают 1 за одинаковое количество шагов. Можно ли построить цепочку из 3 (4, 5,...) подряд идущих чисел с таким же свойством? Конечно. Например, для каждого $k>0$ следующие пять чисел $256k+98, ..., 256k+102$ достигнут 1 за одинаковое количество шагов (для разных $k$ количество шагов будет, конечно, разным). Подобные формулы легко доказывать в лоб и чуть менее легко выводить также в лоб.

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

Scientific American в 1984 г. писал(а):

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

Вот такие смешные рекорды были в 1976 году (и, наверно, держались до 1984). У меня есть основания предполагать, что я являюсь обладателем рекорда сегодняшнего дня (вряд ли кому-то ещё пришло бы в голову потратить несколько дней на составление сносного алгоритма и месяца машинного времени на поиск более высокого результата). Как бы там ни было, мне известен вот такой результат:
5705 подряд идущих чисел, начиная с 2 864 760 066 737 568 достигают 1 за 447 шагов.

Любопытно, что прослеживается весьма чёткая зависимость размеров максимальных кластеров от величины чисел. При этом какой-либо зависимости для количества шагов заметить не удалось.

К сожалению, эти островки постоянства хоть и встречаются часто, но слишком коротки, чтобы как-то помочь с доказательством самой гипотезы.

[Aritaborian]

grizzly в сообщении #988337 писал(а):

У меня есть основания предполагать, что я являюсь обладателем рекорда сегодняшнего дня :D (вряд ли кому-то ещё пришло бы в голову потратить несколько дней на составление сносного алгоритма и месяца машинного времени на поиск более высокого результата). Как бы там ни было, мне известен вот такой результат:
5705 подряд идущих чисел, начиная с 2 864 760 066 737 568 достигают 1 за 447 шагов.

Разве вам неизвестно, что Collatz conjecture уже давно пытаются проверить распределёнными вычислениями? Не знаю, до каких чисел там уже дошли, но наверняка до гораздо бо́льших. (Сам участвовал, но с какого-то момента комп стал из-за этого сильно греться и глючить.)

Впрочем, вы, кажется, не совсем об этом говорите.

[grizzly]

Aritaborian в сообщении #988384 писал(а):

Впрочем, вы, кажется, не совсем об этом говорите.

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

[grizzly]

grizzly в сообщении #988337 писал(а):

Любопытно, что прослеживается весьма чёткая зависимость размеров максимальных кластеров от величины чисел.

Это можно увидеть на графике ниже. Пару слов для пояснения на примере рекорда приведенного выше:
$i$ -- номер рекорда;
$N_i = 2\ 864\ 760\ 066\ 737\ 568$ -- первое число кластера;
$R_i=5705$ -- размер кластера.
На рисунке ниже по оси $OX$ отложено $i$, по оси $OY$ -- $\log_2(N)$.
В этой логарифмической шкале синяя линия отражает зависимость $N_i$ от $i$, а красная -- $R_i^4$ от $i$.



Прослеживается корреляция. Непохоже, чтобы кто-то раньше обратил на это внимание или вообще интересовался подобными закономерностями -- всем намного интереснее убедиться, что до $10^{20}$ гипотеза выполняется. В энциклопедии последовательностей есть самые разнообразные сабжевые рекорды, но список этих там пока отсутствует.

[Три А,да]

Выкладывайте всё, или хотите следить за тем как кто-то проходит по Вашему пути?

[grizzly]

Три А,да в сообщении #992145 писал(а):

Выкладывайте всё, или хотите следить за тем как кто-то проходит по Вашему пути?

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

(несущественное)

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

Что же касается экспериментов типа "вероятностной эвристики", о которых я писал чуть выше, то для придумывания таких экспериментов нужны оригинальные подходы и хоть совсем немного быть в теме. Но для получения результатов это не лучший путь. А для своеобразной цифровой медитации -- самое оно.

Так что любые свежие идеи можете выкладывать. Я не стану больше давить авторитетом своими достижениями

[Три А,да]

Вопрос: есть ли другие, более общие формулировки этой гипотезы.

А чтобы оживить тему: пусть гипотеза выполняется для некоторого $m$
т.е. существует такое $k$, что $f^k(m)=1$
рассмотрим $m+z$
$f^k(m+z)=1+\frac{3^nz} {2^{k-n}}$
Далее, "навешивая" операторы по принципу $BBA$
$(BBA)^c(f^k(m+z))=1+\frac{3^nz} {2^{k-n}}(\frac 3 4)^c$
что в пределе при стремлении $c$ к бесконечности даст искомую единичку.

[Soul Friend]

есть ли простая и явная формула деления чётного числа, вида $3(2n+1)+1$, на два до тех пор пока не получится нечётное число? У меня получается очень долгая и нудная процедура.
Как заранее узнать эту степень двойки?

[Someone]

Soul Friend в сообщении #1340856 писал(а):

Как заранее узнать эту степень двойки?

Может быть, Вы ещё хотите иметь готовую формулу для разложения на простые множители любого натурального числа?

[Dmitriy40]

Soul Friend в сообщении #1340856 писал(а):

Как заранее узнать эту степень двойки?

Записать число в двоичном виде (а в компе оно может быть уже изначально в нём) и посчитать младшие нули (одна команда процессора). Правда это не формула ...

[Someone]

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

Правда это не формула ...

И операций (для перевода в двоичную систему) не меньше.

[Soul Friend]

Пишу небольшую статью, раскрывающую внутреннюю структуру, взаимосвязь чисел-градин, а также доказывающую что кроме цикла 4,2,1 больше циклов нет. Хочу потом выложить её в arXiv.org, но у меня нет доступа, может, поможет кто с инвайтом ?