2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Измененная проблема Коллатца
Сообщение16.11.2018, 20:18 


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

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

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

 Профиль  
                  
 
 Re: Измененная проблема Коллатца
Сообщение17.11.2018, 01:38 
Заслуженный участник
Аватара пользователя


09/09/14
6328
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, а наибольшее -- с полсотни цифр. И рекордное количество шагов растёт здесь линейно от числа, а у Коллатца -- логарифмически.

 Профиль  
                  
 
 Re: Измененная проблема Коллатца
Сообщение17.11.2018, 02:10 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Измененная проблема Коллатца
Сообщение17.11.2018, 02:40 


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

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

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

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


21/11/12
1870
Санкт-Петербург
Несколько соображений по стандартному Коллатцу, чтобы не поднимать старое. Переформулируем процедуру так: $\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)$ могут быть получены сами из себя, то проблема решена (если бы из одного, к примеру, следовало бы вхождение другого с фиксированной разностью номеров). Может это и не сложно.

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


21/11/12
1870
Санкт-Петербург
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$, которую можно продолжить и дальше. Так что круг объектов, требующих доказательства сужается до бесконечности, что равносильно доказательству :)

 Профиль  
                  
 
 Re: Измененная проблема Коллатца
Сообщение19.11.2018, 20:33 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
Нет, это слишком лихо. Предыдущий пост можно не читать.

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


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

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



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

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


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

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