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

[LionKing]

У кого какие мысли по поводу этой гипотезы?
Формулировка гипотезы:
Есть числовая последовательность $\{ 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$.

[bot]

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

[vicvolf]

Цитата:

У кого какие мысли по поводу этой гипотезы?

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

[Sonic86]

поиск по форуму
Уже несколько тем было. Может там даже и не все.
Википедия - Вот тут какая-то навороченная pdf-ка есть. Можете попробовать почитать - вдруг поймете.
А так...

bot в сообщении #568357 писал(а):

Проблема известная и нерешённая - вот и все мысли.

[LionKing]

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

-- 08.05.2012, 16:23 --

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

[vicvolf]

LionKing в сообщении #568754 писал(а):

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

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

[Утундрий]

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

[LionKing]

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

[Три А,да]

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 $ - нечетное натуральное число;
Но это уже на десерт

[Lia]

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

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

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

[Deggial]

Пост возвращён

[Три А,да]

В последнем утверждении:

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

если $ m $ - нечетное натуральное число;

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

[grizzly]

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

Лучше так:
...

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

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

[grizzly]

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

Для упрощения записи в терминах используется префикс "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) и найти расходящуюся последовательность не удалось (просмотрено несколько млрд чисел в начале натурального ряда). Нетривиальных циклов здесь обнаружено не было.

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

[Три А,да]

Спасибо за ссылку, буду изучать.

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

Введём следующие обозначения для операторов:
$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$