2014 dxdy logo

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

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




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


09/09/14
6328
Три А,да в сообщении #987938 писал(а):
Интересные свойства этих операторов:

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

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

 Профиль  
                  
 
 Re: Гипотеза Колатца
Сообщение10.03.2015, 04:07 


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

 Профиль  
                  
 
 Re: Гипотеза Колатца
Сообщение10.03.2015, 19:36 


07/10/06
77
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$, правда шаги уже будут другие.

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


09/09/14
6328
Три А,да

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

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

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

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

 Профиль  
                  
 
 Re: Гипотеза Колатца
Сообщение10.03.2015, 22:07 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
grizzly в сообщении #988337 писал(а):
У меня есть основания предполагать, что я являюсь обладателем рекорда сегодняшнего дня :D (вряд ли кому-то ещё пришло бы в голову потратить несколько дней на составление сносного алгоритма и месяца машинного времени на поиск более высокого результата). Как бы там ни было, мне известен вот такой результат:
5705 подряд идущих чисел, начиная с 2 864 760 066 737 568 достигают 1 за 447 шагов.
Разве вам неизвестно, что Collatz conjecture уже давно пытаются проверить распределёнными вычислениями? Не знаю, до каких чисел там уже дошли, но наверняка до гораздо бо́льших. (Сам участвовал, но с какого-то момента комп стал из-за этого сильно греться и глючить.)

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

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


09/09/14
6328
Aritaborian в сообщении #988384 писал(а):
Впрочем, вы, кажется, не совсем об этом говорите.

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

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


09/09/14
6328
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}$ гипотеза выполняется. В энциклопедии последовательностей есть самые разнообразные сабжевые рекорды, но список этих там пока отсутствует.

 Профиль  
                  
 
 Re: Гипотеза Колатца
Сообщение18.03.2015, 19:40 


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

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


09/09/14
6328
Три А,да в сообщении #992145 писал(а):
Выкладывайте всё, или хотите следить за тем как кто-то проходит по Вашему пути?

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

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

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

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

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

 Профиль  
                  
 
 Re: Гипотеза Колатца
Сообщение22.03.2015, 13:29 


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

А чтобы оживить тему: пусть гипотеза выполняется для некоторого $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$ к бесконечности даст искомую единичку.

 Профиль  
                  
 
 Re: Гипотеза Колатца
Сообщение23.09.2018, 10:10 
Аватара пользователя


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

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


23/07/05
17973
Москва
Soul Friend в сообщении #1340856 писал(а):
Как заранее узнать эту степень двойки?
Может быть, Вы ещё хотите иметь готовую формулу для разложения на простые множители любого натурального числа?

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


20/08/14
11065
Россия, Москва
Soul Friend в сообщении #1340856 писал(а):
Как заранее узнать эту степень двойки?
Записать число в двоичном виде (а в компе оно может быть уже изначально в нём) и посчитать младшие нули (одна команда процессора). :mrgreen: Правда это не формула ...

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


23/07/05
17973
Москва
Dmitriy40 в сообщении #1340880 писал(а):
Правда это не формула ...
И операций (для перевода в двоичную систему) не меньше.

 Профиль  
                  
 
 Re: Гипотеза Колатца
Сообщение23.09.2018, 19:28 
Аватара пользователя


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

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

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



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

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


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

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