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
5904
Новосибирск
Проблема известная и нерешённая - вот и все мысли. Каких ещё мыслей ждёте?

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


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

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

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


08/04/08
8556
поиск по форуму
Уже несколько тем было. Может там даже и не все.
Википедия - Вот тут какая-то навороченная 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
3110
LionKing в сообщении #568754 писал(а):
Подходов, как это обычно бывает в подобных ситуациях, просто уйма, прорва! Но вот какой из них приведет к желанному финалу? На каких уже были сломаны копья?
-- 08.05.2012, 16:23 --
Кстати, а что если использовать разработки Андре Семереди?

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

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


15/10/08
11536
Можно несколько облегчить (хотя бы численное) исследование проблемы, если заметить, что по сути все переходы в конце-концов (т.е. после достаточно большого числа шагов) совершаются только между числами вида $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  След.

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



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

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


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

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