Измененная проблема Коллатца

[daniel starodubtsev]

Возьмем некоторое натуральное число. Будем применять к нему следующие операции:

Если оно делится на три, поделим его на три
Если оно дает остаток 1 при делении на три, то умножим его на 5
Если оно дает остаток 2 при делении на три, то умножим его на два и прибавим два

То же самое с получившимся числом и так далее.
Вопрос: любое ли число рано или поздно придет к 2 или 130 (после чего зациклится)?

[grizzly]

daniel starodubtsev в сообщении #1354575 писал(а):

Если оно делится на три, поделим его на три
Если оно дает остаток 1 при делении на три, то умножим его на 5
Если оно дает остаток 2 при делении на три, то умножим его на два и прибавим два

По сути, вы делаете следующее:

if (a%3==0, a=a/3); 
if (a%3==1, a=(a*10+2)/3); 
if (a%3==2, a=(a*2+2)/3); 

И если предположить, что в среднем это всё равномерно распределяется по модулю 3, то, опять таки в среднем, последовательность должна быстро уменьшаться. Это, конечно, ничего не гарантирует и вряд ли доказать что-то будет сильно проще, чем в стандартом Коллатце, но и не так интересно. Если посмотреть эвристику, так и получается: всё очень быстро скатывается в эти 2 цикла (я посмотрел пару млн. чисел -- почти никто не выходит за рамки 1000 циклов (как выше). И "градины" тоже какие-то все скромные.

Другое дело, что из тех же вероятностных соображений можно эту последовательность улучшить до такой (я изменил вторую строчку):

if (a%3==0, a=a/3); 
if (a%3==1, a=(a*13+2)/3); 
if (a%3==2, a=(a*2+2)/3); 

И тут уже всё намного интересней. По-прежнему, эвристика в пользу ограниченности. Но совсем чуть. Поэтому отдельные числа ведут себя куда круче, чем в обычном Коллатце. Например, есть цикл длинной несколько тысяч шагов с наименьшим значением 397706, а наибольшее -- с полсотни цифр. И рекордное количество шагов растёт здесь линейно от числа, а у Коллатца -- логарифмически.

[Dmitriy40]

Проверил числа до двух миллиардов, ни одно не стало исключением. Максимально требуется до 5000 шагов чтобы отбросить число. Числа в процессе выросли лишь до 49 знаков.

[lel0lel]

Красиво! Числа до одного миллиона Вашу гипотезу не опровергают (уже не актуально, долго набирал сообщение). Вероятно, что гипотеза верна, эвристический аргумент такой же как для гипотезы Коллатца: у Вас случайное число в среднем умножается на 10/27 (у Коллатца на 3/4), значит рано или поздно будет убывание (об этом уже написано выше). Интересно, что в Вашем случае есть два финала (2, 130). Скорее всего, это связано с тем, что у Вас больше различных преобразований (не 2 как у Коллатца, а 3), равное количеству возможных остатков по модулю 3. Интересно проверить: если проводить 4 отличных друг от друга преобразования в зависимости от остатков по модулю 4 будет ли получаться 3 возможных финала?

Погуглив, можно обнаружить, что идея обобщения гипотезы не новая: google.

Добавлю несколько экспериментальных результатов по Вашей гипотезе. Среди чисел до миллиона ровно 947400 чисел имеют финал 2, оставшиеся 52600 имеют финал 130. У числа 449429 самая длинная цепочка с финалом 2 (её длина 2408). У числа 489945 самая длинная цепочка с финалом 130 (её длина 1495).

[Andrey A]

Несколько соображений по стандартному Коллатцу, чтобы не поднимать старое. Переформулируем процедуру так: $\dfrac{3m+1}{2}\ (1)$ для нечетного $m$, $\dfrac{m}{2}\ (0)$ для четного $m$. В таком виде она напоминает процедуру двоичного разложения целого числа от последнего знака к первому. На всякий случай пример для $m=41:\ \dfrac{41-1}{2}=20\ ( \to 1);$ $\dfrac{20}{2}=10 \ ( \to 01);$ $\dfrac{10}{2}=5 \ ( \to 001);$ $\dfrac{5-1}{2}=2 \ ( \to 1001);$ $\dfrac{2}{2}=1 \ ( \to 01001);$ $1 \to 101001.$ $41=101001$. Если теперь поменять $\dfrac{m-1}{2}$ на $\dfrac{3m+1}{2}$, сохраняя последовательность двоичных знаков, то с какого числа нужно начать, чтобы прийти к единице? Движение по прежнему от последнего знака: $\cfrac{\cfrac{\cfrac{\cfrac{\cfrac{3x+1}{2}}{\ \ 2}}{\ \ \ \ 2}\cdot 3+1}{2}}{\ \ 2}=1$ или так: $\cfrac{\cfrac{3x+1}{8}\cdot 3+1}{4}=1$. Запуская обратную процедуру, находим $x=\dfrac{7}{3}$. Выразим это так: $f(41)=\dfrac{7}{3}$ - стартовое значение, начиная с которого двоичная запись числа $41$ приводит по процедуре Коллатца к единице: $\dfrac{\dfrac{7}{3}\cdot 3+1}{2}=4;\dfrac{4}{2}=2;\dfrac{2}{2}=1;\dfrac{1\cdot 3+1}{2}=2;\dfrac{2}{2}=1.$ Такой подход снимает зависимость от промежуточных результатов (чет/нечет), это главное. Функция $f(n)$ есть обратная функция от заявленной в условии, её нетрудно формализовать. Определим последовательность $f(n)$ так:

$$f(1)=1;\ f(2n)=2f(n);\ f(2n+1)=\dfrac{2f(n)-1}{3}.$$

Получаем следующее

$\left.\begin{matrix} n \\ f(n) \end{matrix}\right|$ $\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 2 & \frac{1}{3} & 4 & 1 & \frac{2}{3} & -\frac{1}{9} & 8 & \frac{7}{3} & 2 \end{matrix}$ $\begin{matrix} 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20\\ \frac{1}{3} & \frac{4}{3} & \frac{1}{9} & -\frac{2}{9} & -\frac{11}{27} & 16 & 5 & \frac{14}{3} & \frac{11}{9} & 4 \end{matrix}$ $\begin{matrix} 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30\\ 1 & \frac{2}{3} & -\frac{1}{9} & \frac{8}{3} & \frac{5}{9} & \frac{2}{9} & -\frac{7}{27} & -\frac{4}{9} & -\frac{13}{27} & -\frac{22}{27} \end{matrix}$ $\begin{matrix} 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40\\ -\frac{49}{81} & 32 & \frac{31}{3} & 10 & 3 & \frac{28}{3} & \frac{25}{9} & \frac{22}{9} & \frac{13}{27} & 8 \end{matrix}$ $\begin{matrix} 41 \\ \frac{7}{3} \end{matrix}...$

В сущности, выстраивая цепочки от некоторого целого $m$ к единице по прямой процедуре Коллатца, мы вычисляем двоичную запись номера вхождения $m$ в $f(n)$ (фиксируя при этом нули и единицы в обратном движении), поэтому достаточно доказать, что любое целое число содержится в последовательности $f(n)$. При этом надо учитывать следующее:
1. Если некоторый член последовательности дробный, он уже не может участвовать в образовании целого члена, поскольку в знаменателях, как видим, степени тройки, а не двойки.
2. Если некоторое целое нечетное $m$ входит в $f(n)$, то $m\cdot 2^k$ также входит в нее при любом $k$, поэтому вхождение четных не нуждается в доказательстве.
3. Если целое $f(n)=3k+2$, то $f(2n+1)=\dfrac{2\cdot (3k+2)-1}{3}=2k+1$, поэтому достаточно доказать вхождение всех целых чисел вида $3k+2$, но каждое из них принадлежит либо множеству четных, либо нечетных. Так что из любого целого члена последовательности вырастает множество подпоследовательностей ("обратное дерево"). Если показать, что все они $(f(i)=3k+2)$ могут быть получены сами из себя, то проблема решена (если бы из одного, к примеру, следовало бы вхождение другого с фиксированной разностью номеров). Может это и не сложно.

[Andrey A]

Andrey A в сообщении #1355120 писал(а):

3. Если целое $f(n)=3k+2$, то $f(2n+1)=\dfrac{2\cdot (3k+2)-1}{3}=2k+1$, поэтому достаточно доказать вхождение всех целых чисел вида $3k+2$

Четные члены вида $3k+2$ в доказательстве не нуждаются, подставляя вместо $k \to 2k+1$, получаем $6k+5.$
4. Если целое $f(n)=9k+8$, то $f(2n+1)=\dfrac{2\cdot (9k+8)-1}{3}=6k+5$, поэтому достаточно доказать вхождение всех целых чисел вида $9k+8$.
Четные члены вида $9k+8$ в доказательстве не нуждаются, подставляя вместо $k \to 2k+1$, получаем $18k+17.$ Ну и т.д.

Возникает последовательность $2k+1,6k+5,18k+17, ..., a_{n+1}=3a_n+2$, которую можно продолжить и дальше. Так что круг объектов, требующих доказательства сужается до бесконечности, что равносильно доказательству :)

[Andrey A]

Нет, это слишком лихо. Предыдущий пост можно не читать.

[Andrey A]

Нет, тут что-то не то. То, что каждое целое входит в последовательность $f(n)$, следует из самой процедуры. Тем более известен номер первого вхождения. Но это верно и для других процедур, если правильно установлена обратная функция. Наличие второго цикла просто увеличивает количество номеров вхождения. Непонятно что тут доказывать, и помогает ли это сколько-нибудь делу. Sorry.