2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Гипотеза Колатца
Сообщение07.05.2012, 13:00 


07/05/12

127
У кого какие мысли по поводу этой гипотезы?
Формулировка гипотезы:
Есть числовая последовательность $\{ a[n]: n - \text{натуральное число} \}$:
$a[1]$ - натуральное число;
$a[n+1]=f(a[n])$; для любого натурального $n$;
$f(m)=3m+1$, если $m$ - нечетное натуральное число;
$f(m)=m/2$, если $m$ - четное натуральное число.

Утверждается, что для любого $a[1]$ найдется номер $k$ такой, что $a[k]=1$.

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


21/12/05
5931
Новосибирск
Проблема известная и нерешённая - вот и все мысли. Каких ещё мыслей ждёте?

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


23/02/12
3341
Цитата:
У кого какие мысли по поводу этой гипотезы?

Если Вы подняли этот вопрос, то наверно у Вас есть мысли по решению этой гипотезы! Поделитесь?

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


08/04/08
8562
поиск по форуму
Уже несколько тем было. Может там даже и не все.
Википедия - Вот тут какая-то навороченная pdf-ка есть. Можете попробовать почитать - вдруг поймете.
А так...
bot в сообщении #568357 писал(а):
Проблема известная и нерешённая - вот и все мысли.

 Профиль  
                  
 
 Re: Гипотеза Колатца
Сообщение08.05.2012, 15:23 


07/05/12

127
Подходов, как это обычно бывает в подобных ситуациях, просто уйма, прорва! Но вот какой из них приведет к желанному финалу? На каких уже были сломаны копья?

-- 08.05.2012, 16:23 --

Кстати, а что если использовать разработки Андре Семереди?

 Профиль  
                  
 
 Re: Гипотеза Колатца
Сообщение10.05.2012, 09:22 


23/02/12
3341
LionKing в сообщении #568754 писал(а):
Подходов, как это обычно бывает в подобных ситуациях, просто уйма, прорва! Но вот какой из них приведет к желанному финалу? На каких уже были сломаны копья?
-- 08.05.2012, 16:23 --
Кстати, а что если использовать разработки Андре Семереди?

Не понятна цель темы! Вы хотите, чтобы вместо Вас разбирали возможные методы ее решения? :D Ну хотя бы сделайте обзор возможных методов решения и дайте им оценку.

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


15/10/08
12440
Можно несколько облегчить (хотя бы численное) исследование проблемы, если заметить, что по сути все переходы в конце-концов (т.е. после достаточно большого числа шагов) совершаются только между числами вида $1+ 6 \mathbb{Z}$ и $5+ 6 \mathbb{Z}$. По-видимому, все упорядочивание задачи только к тому и сводится, потому как глядя на график зависимости $x_{n + 1}  = f\left( {x_n } \right)$ на ум приходит разве что Фейгенбаум и прочий динамический хаос, в сторону которого, скорее всего, и надобно копать.

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


07/05/12

127
Спасибо, Утундрий. Я уже получил этот результат. А если быть более точным, то первое нечетное натуральное число последовательности чисел-градин может быть любым, а все последующие имеют виды: $6Z+1, 6Z+5$. Сейчас мне кажется, что скоро эта проблема перестанет быть проблемой. Как раз исследую один из методов, и вроде бы он не тупиковый...

 Профиль  
                  
 
 Re: Гипотеза Колатца
Сообщение05.03.2015, 23:42 


07/10/06
77
LionKing в сообщении #568263 писал(а):
У кого какие мысли по поводу этой гипотезы?
Формулировка гипотезы:
Есть числовая последовательность $\{ a[n]: n - \text{натуральное число} \}$:
$a[1]$ - натуральное число;
$a[n+1]=f(a[n])$; для любого натурального $n$;
$f(m)=3m+1$, если $m$ - нечетное натуральное число;
$f(m)=m/2$, если $m$ - четное натуральное число.

Утверждается, что для любого $a[1]$ найдется номер $k$ такой, что $a[k]=1$.


Лучше так:

$ a[1] $ - натуральное число;
$ a[n+1]=f(a[n])$ для любого натурального n;
$ f(m)=m/p$ , если $ \bmod(m,p)=0 $
иначе
$ f(m)=(k+1)m+p-\bmod(m,p)$
где $p=2^z$
$ z$ - натуральное число
Утверждается, что для любого $ a[1] $ найдется номер $ k $ такой, что $ a[k]=1 $

Можно рассмотреть и
$ a[1] $ - натуральное число;
$ a[n+1]=f(a[n]) $ для любого натурального n;
$ f(m)=m/p $, если $ \bmod(m,p)=0 $
иначе
$ f(m)=(k+1)m+p-\bmod(m,p)$ , если $ m $ - нечетное натуральное число;
Но это уже на десерт

 Профиль  
                  
 
 Posted automatically
Сообщение06.03.2015, 00:05 


20/03/14
12041
 i  Сообщение перемещено из форума «Дискуссионные темы (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);

Исправьте все ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 Профиль  
                  
 
 Re: Гипотеза Колатца
Сообщение07.03.2015, 15:54 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  Пост возвращён

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


07/10/06
77
В последнем утверждении:
Три А,да в сообщении #986178 писал(а):
если $ m $ - нечетное натуральное число;

конечно нужно убрать. Забыл убрать при копировании.

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


09/09/14
6328
Три А,да в сообщении #986178 писал(а):
Лучше так:
...

Вряд ли лучше. Но я думаю, что Вы сказали не совсем то, что хотели. Прокомментируйте, пожалуйста, идею словами и дайте пару примеров (но это только если Вы желаете заинтересовать побольше людей своим сообщением).

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

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


09/09/14
6328

(Интуитивно понятные обозначения)

Для упрощения записи в терминах используется префикс "C-" (от Collatz).

    C-функция: $C(n) = 3n+1$ для нечётного $n$ и $n/2$ для чётного.
    C-последовательность -- последовательность чисел, полученных в ходе C-итераций, начиная от некоторого стартового номера $N$.
    C-цикл -- периодическая подпоследовательность C-последовательности. На сегодняшний день известен только один (тривиальный) цикл -- 4,2,1.

I. Вероятностная эвристика.

Вероятностные соображения показывают, что в среднем ожидается уменьшение следующего нечётного члена C-последовательности в 3/4 раза относительно предыдущего нечётного. Объясняется это простой формулой:
$$\left(\frac32\right)^{1/2} \cdot \left(\frac34\right)^{1/4} \cdot \left(\frac38\right)^{1/8} \cdot ... = \frac34.$$
(Очевидно, к вопросу существования C-циклов эти вероятностные рассуждения неприменимы -- речь идёт только об ограниченности C-последовательности.)

Возникает интерес посмотреть -- а что если немного изменить формулировку C-функции так, чтобы эти самые 3/4 сделать намного ближе к 1. Интересно посмотреть как со стороны 1+, так и со стороны 1-. Ниже описаны оба эксперимента.

Эксперимент 1.
Возьмём C-функцию и, скажем так, обрежем в ней "высокие частоты". По-прежнему нечётное число n переходит в $3n+1$; число, которое делится на $2^5$ (и для более высоких степеней), также переходит в $3n+1$; чётные числа меньшей чётности -- в $n/2$.

(Формальная запись и примеры)

Формальное обозначение:
$$C_{32}(n) = \begin{array}{ll}
3n+1, & n=0(\bmod \ {32})\\
3n+1, & n=1(\bmod \ 2)\\
n/2,  & \text{для других } n.
\end{array}$$

Примеры C32-последовательностей для стартовых номеров 7, 15, 331:
    7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 (совпадает с оригинальной C-последовательностью).
    15, 46, 23, 70, 35, 106, 53, 160, 481, ..., 23 -- (C32-цикл длиной 194).
    331, 994, 497, 1492, 746, 373, 1120, 3361, 10084, 5042, 2521, 7564, 3782, 1891, 5674, 2837, 8512, ... (предположительно расходящаяся -- прослежено до 20000-значного числа).

Для C32-функции аналогичный коэффициент среднего ожидаемого прироста становится чуть больше 1 (~1.005) и, действительно, для многих (около 1% в начале натурального ряда) стартовых $N$ C32-последовательности предположительно расходятся. Я говорю "предположительно", поскольку доказать расходимость, например, C32(331) вряд ли проще, чем всю оригинальную C-гипотезу.

Эксперимент 2.
Построим по аналогии с предыдущим C64-функцию.
$$C_{64}(n) = \begin{array}{ll}
3n+1, & n=0(\bmod \ 64)\\
3n+1, & n=1(\bmod \ 2)\\
n/2,  & \text{для других } n.
\end{array}$$
Здесь соответствующий коэффициент среднего ожидаемого прироста меньше 1 (около 0,88) и найти расходящуюся последовательность не удалось (просмотрено несколько млрд чисел в начале натурального ряда). Нетривиальных циклов здесь обнаружено не было.

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

 Профиль  
                  
 
 Re: Гипотеза Колатца
Сообщение09.03.2015, 22:10 


07/10/06
77
Спасибо за ссылку, буду изучать.

Выложу кое-что, пока "игрался":

Введём следующие обозначения для операторов:
$A(m)=3m+1$
$B(m)=m/2$

Тогда, согласно гипотезе Коллатца для любого нечётного $m$ есть некоторая последовательность таких операторов
$B^{k_n}(A(B^{k_n-1}...A(B^{k_2}(A(B^{k_1}(A(m)))))))=1$
$k_i$ и $k_j$ могут как совпадать, так и отличаться

Интересные свойства этих операторов:
$A(B^{k}(m))=B^{k}(A(m)+M_{k})$
$A(M_{k})=M_{k+1}+M_{k}$

где $M_{k}$ - числа Марсенна

Дальше можно всё перенести и рассматривать:
$B^{k_n+k_{n-1}+...+k_2+k_1}(A^k(m)+R)=1$
где $R$ - конечный ряд, получаемый после всех перестановок операторов
Можно показать, что существует некое натуральное $z$ такое, что
тогда $A^k(m)+z=2^{k_n+k_{n-1}+...+k_2+k_1}$

вопрос в том, чтобы показать, что $R=z$

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

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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