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

[Soul Friend]

Да, граф Коллатца это общая формулировка дробей Коллатца. Записей в виде дробей там нет.
Перевод гуглтранслейта:
https://translate.googleusercontent.com ... UvBeaANuGg
Можно скопировать и вставить в русскоязычную версию статьи в wikipedia.
Попробую записать дробь Коллатца:
$f^i x_i \, | \, x_{i}=f(x_{i-1},y)=\frac{x_{i-1} \cdot 2^y-1}{3} \, \& \, x, y\in N$;

(Оффтоп)

вспомнилось:

Евгений Машеров в сообщении #1254769 писал(а):

Более тонкое жульничество, когда в значение одной переменной втиснут значения других, например, так, чтобы в двоичной записи единственного аргумента первый, n+1, 2n+1 и т.д. биты были битами первой переменной, второй и далее - второй, третий... и так до энной, а в функции была бы "распаковка".

[Soul Friend]

Допустим, имеем такую дробь Коллатца:

$$\frac{\frac{2^{k_i}-1}{3} \cdot 2^{k_{i-1}}-1}{3}_{...}_{\frac{\frac{2^{k_2}-1}{3} \cdot 2^{k_1}-1}{3}}$$

которая равна натуральному числу. Тогда, для каждой степени двойки $2^{k_x}$ имеем множество других степеней вида $2^{k_x+(3^x-3^{x-1})n}$, $n\geqslant 1, n \in N$ ; любыми из которых можем заменить степень $2^{k_x}$ и получить другое целочисленное (натуральное) решение дроби.
$k_1, k_2, ... , k_i$ - это разные натуральные числа.

Пример:
$k_1=\{0, 2, 4, 6, 8, 10, ...\}$
$k_2=\{2, 8, 14, 20, 26, ...\}$
$k_3=\{2, 20, 38, 56, ...\}$
для: ${\frac{\frac{\frac{2^{k_3}-1}{3} \cdot 2^{k_2}-1}{3} \cdot 2^{k_1}-1}{3}}$

[Soul Friend]

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

Тогда, для каждой степени двойки $2^{k_x}$ имеем множество других степеней вида $2^{k_x+(3^x-3^{x-1})n}$, $n\geqslant 1, n \in N$ ; любыми из которых можем заменить степень $2^{k_x}$ и получить другое целочисленное (натуральное) решение дроби.

В зависимости от $n$, приравняем результат вычисления такой дроби к $A_n$, тогда соотношения конечных разностей $A$ будет:

$$\frac{A_{n+1}-A_{n}}{A_{n}-A_{n-1}}=2^{3^x-3^{x-1}}$$

где $x$ это нижний индекс показателя степени $K$ связанного с $n$, (индекс степени двойки изменяемой части дроби)

[MerkulovaLE]

Добрый день!

Мое предложение - рассматривать троичную систему счисления.

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

Обращаюсь к коллективному разуму для проверки идеи.

[Soul Friend]

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

В зависимости от $n$, приравняем результат вычисления такой дроби к $A_n$, тогда соотношения конечных разностей $A$ будет:

$$\frac{A_{n+1}-A_{n}}{A_{n}-A_{n-1}}=2^{3^x-3^{x-1}}$$

где $x$ это нижний индекс показателя степени $K$ связанного с $n$, (индекс степени двойки изменяемой части дроби)

также и $n$ с индексом $x$ :

$$\frac{A_{n_x+1}-A_{n_x}}{A_{n_x}-A_{n_x-1}}=2^{3^x-3^{x-1}}$$

[vladimirmir2012]

Возьмите любое число. Если оно чётное, поделите его на два. Если нечётное, умножьте на три, прибавьте один. Повторите. Любое ли число в итоге приходит к 1?

Выполняя, заданные действия любое произвольное число в некоторый момент становится <= 500.
Теперь осталось попросить любого программиста написать алгоритм, который проверяет "сходятся" ли все числа <= 500 к 1.

[mihaild]

vladimirmir2012 в сообщении #1433819 писал(а):

любое произвольное число в некоторый момент становится <= 500

Вы это умеете доказывать?

vladimirmir2012 в сообщении #1433819 писал(а):

"сходятся" ли все числа <= 500 к 1

Сходятся. Гипотеза Коллатца давно проверена для гораздо большего диапазона (чуть больше чем для $10^18$, если верить википедии).

[vladimirmir2012]

Понял о чем вы.
Мы же в некоторый момент умножаем на три.

[Sender]

MerkulovaLE в сообщении #1388683 писал(а):

Мое предложение - рассматривать троичную систему счисления.

Посмотрите, например, как преобразуется число $27=1000_3.$

[grizzly]

Тег "городские легенды в математике" :)

mihaild в сообщении #1433823 писал(а):

чуть больше чем для $10^{18}$, если верить википедии).

Не нужно верить. Там какое-то странное число, даже с первого взгляда не догадаешься, что это $2^{60}$. Любопытно, кто это первым придумал. В Википедии оно появилось ещё в 2018 г., а фраза "по состоянию на апрель 2019" появилась позже (и гуглится уже во многих новостях на языках бывшего Союза).

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

[MerkulovaLE]

Ответ Sender

Тройки в любой степени можно не рассматривать,
так как в дальнейшей последовательности их не
окажется. Нужно рассматривать не $27$,
а сразу $28$.

В любом случае, спасибо за внимание.

[Rulin]

Вот такой вопрос, а почему гипотезу не рассматривают с точки зрения теории вероятности?
Потому, что при определённых допущениях гипотезу можно свести к игре
1 раунд , с вероятностью 50% увеличиваем на 3n+1 ,
2-й раунд точно уменьшаем в 2 раза.

Итого на когда орёл, увеличиваем в 1,5 раза+1, решка уменьшаем в 2 раза.
Если у нас 500 орлов и 500 решек и 1000 чисел около миллиона, то тогда до хода их сумма будет миллиард.
После хода 500 чисел станут около 1,5 млн +1 , а 500 чисел станут равным около 0,5 млн.
В среднем сумма 1000 чисел после преобразования увеличилась на 1000 . За счёт того, что половина чисел укрупнились, а половина - уполовинились.
Из этих 500 чисел далее 250 увеличаться, а 250 уменьшаться. Но сумма выборки из 1000 чисел останется прежней. Ну то есть опять на 1000 увеличиться.
В вскоре малая часть из выборки в 1000 чисел будет «вбирать в себя» всю сумму этой выборки из 1000 чисел.
Если у нас конечная выборка из 1000 чисел, то конечно рано или поздно на N шаге ему «не повезёт» и оно начнёт уменьшаться. Но если у нас бесконечное число натуральных чисел, то сколько бы не было шагов, всегда останутся числа, которые будут только расти.
Но это только если вероятность у нас равна строго 1/2 , а не меняется.
Чтобы проверить на реальных числах я создал программу, которая прогоняет все числа от 4 млд, до 4 млд 100 млн.
Изначальная сумма выборки из 100 млн. чисел будет равна 405 000 000 050 000 000.
После первого прогона сумма выборки равна 708 750 000 025 000 000.
Ну это понятно почему. У нас половина чисел утроилась, а половина в 2 раза упала.
2 прогона
480 937 500 037 500 000
А вот тут уже интереснее, как видно, у нас общая сумма выборки возросла.
4 прогона
523 652 343 871 875 000 – опять возрастание.
26 прогонов
578 475 352 178 380 277
Какие-то числа , вполне вероятно, давно уже сошлись к 1, но остальные увеличились. Да так, что сумма выборки у нас возрасла.
50 прогонов
578 290 145 872 577 706
Сумма выборки упала.
Но вот, что интересно. Разделим нашу выборку из 100 млн чисел на 100 выборок по 1 млн. чисел. И оказывается, что сумма
Худшей - 5 553 184 626 781 366
Медианной -5 757 474 112 517 336
Лучшей - 6 079 971 308 234 795
То есть разные миллионы проявляют разные свойства. В одном миллионе больше удачных чисел, чем в другом.
76 прогонов
588 249 777 938 152 191
Худший - 4 725 764 146 461 573
Медианный -5 738 145 153 358 704
Лучший - 11 892 075 883 659 233

Как видим, на уровне в 1 млн. у нас идёт уже снижение суммы. Но зато лучший миллион чисел показал резкий рост.
100 прогонов
Сумма 594 388 504 161 159 273
Худший - 3 691 594 816 527 496
Медианный - 5 431 830 526 460 662
Лучший - 28 197 860 931 263 345
Опять в среднем каждый отдельный миллион сходиться к единице. Но лучший миллион от неё стремительно уходит.

120 прогонов
633 858 644 853 351 223
Худший - 2 654 262 478 896 087
Медианный - 4 745 698 373 166 673
Лучший - 42 500 437 803 337 059

140 прогонов
987 015 688 353 867 620
Худший - 2 236 248 995 761 699
Медианный - 4 127 340 049 605 814
Лучший - 381 229 779 048 522 611

Если в лучшем миллионе выделить лучшие и худшие тысячи т .д. , то наверняка будет такое же распределение.
Так что в целом пока я вижу, что лучшие числа до поры до времени увеличиваются и сумма выборки чисел тоже увеличивается(но возможно это потому, что мы удачную выборку нашли).
Мне трудно представить, что в условиях верности гипотезы Коллатца будут такие результаты численных экспериментов.

[grizzly]

Rulin в сообщении #1476439 писал(а):

Вот такой вопрос, а почему гипотезу не рассматривают с точки зрения теории вероятности?

Если бы Вы посмотрели какой-нибудь популярный обзор по теме, были бы сильно удивлены. Хотя бы вот эту ссылку из руВики.

Rulin в сообщении #1476439 писал(а):

Итого на когда орёл, увеличиваем в 1,5 раза+1, решка уменьшаем в 2 раза.

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

[Rulin]

Цитата:

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

-ну так вероятность "нарваться" на число, которое делиться на 4 будет 1/4, которая на 8 будет 1/8 и т.д. Я про изначальную выборку. Но и дальше я делаю предположение , что в каждой "модифицированно" выборке будут такие же вероятности. То есть я не только как вы выразились "осознал", но и дальше предположил.

Цитата:

Если бы Вы посмотрели какой-нибудь популярный обзор по теме, были бы сильно удивлены. Хотя бы вот эту ссылку из руВики.

- Нет, это неправильно. Т.к. у автора
"Consequently this heuristic argument suggests that on average the iterates in a trajectory tend to shrink in size"
Это у него вывод такой , потому, что он рассматривает каждое отдельное число.
А надо рассматривать не каждое отдельное число, а совокупность чисел.
А совокупность чисел имеет тенденцию к росту.

Например вот в этой статье подробно описано-
https://aftershock.news/?q=node/815990&full

Там тоже каждый конкретный игрок проигрывает. Но совокупность в целом выигрывает.

Я утвержаю , что для каждого числа n шагов мы можем подобрать совокупность размером M , при котором она за n шагов будет статистически расти. А значит в ней будут числа, которые будут расти.

[grizzly]

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

(И чтоб не вставать два раза.) Если ни того ни другого Вам делать не хочется, тогда берите хотя бы в 10 раз больше шагов, а то 140 на миллиардах это просто смешно при таком подходе.