Внутре гипотезы Коллатца

[Dmitriy40]

MGM в сообщении #1618955 писал(а):

$m_1$ (если имеется в виду последний шаг перед 1) всегда $2^{2n}$. Легко доказывается.

Это понятно: только такие степени двойки имеют остаток $1\bmod3$ и соответственно могут получиться предшествующей операцией $3x+1$.
Вопрос увидеть пример $m_1>4$ для минимальных $R_n$. До $10^{14}$ таковых не обнаружено. Не для минимальных - тривиально, можно построить например обратным ходом.
Из чисел вида $2^x-1$ минимальные $R_n$ дали только $x=2,3,5$ для $n=2,5,39$ (во всяком случае для $x<47$).

-- 20.11.2023, 21:30 --

MGM в сообщении #1618955 писал(а):

Однако, если считать все нечетные меньшие $2^{n}- 1$ подряд, [...]
Моего терпения хватило только до $n=30$. Дальше - часы ожидания.

Ну, смотря как и на чём писать программу. У меня в один поток считалось со скоростью около 140млрд/ч (т.е. около 7ч на триллионный интервал, а первый миллиард вообще секунд за 15).

[waxtep]

Dmitriy40 в сообщении #1618698 писал(а):

У меня две новости, и обе хорошие

И у меня кажется наконец хорошая новость, правда одна Верю, что нашел разумный алгоритм расчета $R_n^{\min}$ (работающий быстрее сплошного перебора, начиная с достаточно больших $n$).
Смотрите:
1) $R_n^{\min}$ за один шаг приходит к какому-то числу вида $6k+1$ или $6k+5$; при этом, это наименьшие числа "класса" $n-1$ своего "рода" (т.е. дающие $1$ или $5$ по модулю $6$)
2) Эти два числа за шаг приходят к шести числам класса $n-2$, наименьшим в родах $1,5,7,11,13,17\bmod18$
...
n-1) Мы приходим к $2\cdot3^{n-1}$ числам первого класса, каждое из которых минимально в своем роду $\pmod{2\cdot3^{n}}$ (здесь все значения остатков, не делящиеся на три)

В таком виде задача, конечно, необозрима: огромное количество исходных кандидатов в первом классе, причем многие из них сами чудовищного размера. Здесь самое время вспомнить эвристику $s_n=\sum\ind_{i=1}^{n}{m_i}\approx\frac53n$. Это значит, слишком далеко бегать по получающемуся дереву не нужно: кандидатов первого класса может быть всего $\approx\frac23n$, а не $2\cdot3^{n-1}$. Это обозримо; к тому же, на каждом шаге будет фильтрация недопустимых значений по модулю $3$.

Проиллюстрирую на примере поиска $R_9^{\min}=43$, на котором обламывали зубья все мои более примитивные инструменты. Я немного сжульничаю и возьму $s_9=20>\frac53\cdot9=15$; это оправдано, для маленьких $n<50$ эвристика плохо работает; в общем, накинем немного, на фоне точного значения $2\cdot3^{8}=13122$ это ерунда. Пройдемся по дереву снизу вверх:

$m_1=4+2p$, при этом (по эвристике) должно выполняться $m_1+8\leqslant20$ ($8$ - это если остальные восемь $m_i$ принимают минимальное значение единица)- подходят только четные $4\leqslant{m_1}\leqslant12$; здесь я тоже сжульничаю и буду рассматривать только $m_1=4\Rightarrow{R_1=5}$ (это необязательно, просто в данном случае цепочки $m_i$ с $m_1>4$ заведомо не содержат решения и довольно быстро "загнутся"; в общем случае, для еще не найденных $R_n^{\min}$ так делать не следует; далее уже жульничать не будем); кстати же, $m_1=6$ мы бы и так отбросили, поскольку соответствующее ему $R_1=\frac13(2^6-1)=21$ делится на три и интереса не представляет;

$R_1=5\equiv2\pmod3$, и мы помним, что сумма всех $m_i$ не должна превзойти $20$, значит, далее возможны только такие цепочки для $R_2$ (Dmitriy40, простите, здесь все таки буду записывать $m_1$ слева, а $m_n$ справа, а то запутаюсь):

$$\begin{array}{l}R_2=\\ (4,1)=3\text{ - неинтересно, т.к. делится на 3}\\ (4,3)=13\\ (4,5)=53\\ (4,7)=213\quad\text{- неинтересно, т.к. делится на 3}\\ (4,9)=853\end{array}$$

Аналогично, пририсовываем справа нечетное $m_3$ для $R_2\equiv2\pmod3$ и четное $m_3$ для $R_2\equiv1\pmod3$, не забывая, что в сумме все $m_i$ не должны превысить $20$, а так же выкидывая из дальнейшего рассмотрения получающиеся $R_3$, которые делятся на $3$:

$$\begin{array}{l}R_3=\\ (4,3,2)=17\\ (4,3,6)=277\\ (4,5,1)=35\\ (4,5,5)=565\end{array}$$

$$\begin{array}{l}R_4=\\ (4,3,2,1)=11\\ (4,3,2,5)=181\\ (4,5,1,1)=23\\ (4,5,1,5)=373\end{array}$$

$$\begin{array}{l}R_5=\\ (4,3,2,1,1)=7\\ (4,3,2,1,3)=29\\ (4,3,2,5,2)=241\\ (4,5,1,1,3)=61\\ (4,5,1,1,5)=245\end{array}$$

$$\begin{array}{l}R_6=\\ (4,3,2,1,1,4)=37\\ (4,3,2,1,1,6)=149\\ (4,3,2,1,3,1)=19\\ (4,3,2,1,3,3)=77\\ (4,5,1,1,5,1)=163\end{array}$$

$$\begin{array}{l}R_7=\\ (4,3,2,1,1,4,2)=49\\ (4,3,2,1,3,1,2)=25\\ (4,3,2,1,3,1,4)=101\end{array}$$

$$\begin{array}{l}R_8=\\ (4,3,2,1,1,4,2,2)=65\\ (4,3,2,1,3,1,4,1)=67\end{array}$$

$$\begin{array}{l}R_9^{\min}=\\ (4,3,2,1,1,4,2,2,1)=43\end{array}$$

Бинго! Это я хочу (и кажется могу) запрогать.

[Dmitriy40]

Да, я тоже думал над перебором $m_i$ в сторону увеличения, только собирался брать вектор сразу нужной длины и пытаться заполнять его с младших. Но до формализации ограничений руки так и не дошли.

[waxtep]

Dmitriy40 в сообщении #1618984 писал(а):

Да, я тоже думал над перебором $m_i$ в сторону увеличения, только собирался брать вектор сразу нужной длины и пытаться заполнять его с младших. Но до формализации ограничений руки так и не дошли.

Я в эту штуку прям верю - ну надо напрогать и проверить промышленно; сделаю не торопясь и криво. Конечно, она опирается на недоказанную эвристику, но зато наводит (если работает) какой-никакой порядок в бессистемных скачках "градин". Вообще, задача в такой постановке получается родственной с минимизацией сумм определенного вида и с разложением натурального числа в сумму заданного количества других натуральных, при определенных ограничениях. Так что не удивлюсь, если на эту тему есть известные результаты, я не пытался искать в литературе.

Еще пара соображений:
1) Алгоритм, запущенный для какого-то $n$, должен давать не только $R_n^{\min}$, но и все $R_k^{\min},k<n$

2) Я мог не жульничать, ведь эвристика выглядит как $s_n\approx\frac53n+7$, и можно было взять $s_9\leqslant22$; на результат бы не повлияло, только более честно показало бы объем вычислений. Ну, для иллюстрации, мне кажется, мелкое жульничество допустимо

-- 21.11.2023, 00:00 --

MGM в сообщении #1618955 писал(а):

$m_1$ (если имеется в виду последний шаг перед 1) всегда $2^{2n}$. Легко доказывается.
Только это ничего не дает. Проблема глухая. Если идти путем алгебраических манипуляций.

Только все таки $m_1=4+2p,p\in\mathbb{N}_0$; у меня $m$ с каким-нибудь индексом - это степень двойки, на которую делится $3x+1$. Из всего, до чего дотянулись мои корявые ручки, только зависимость суммы этих $m$ от числа утроений выглядит гладко и ладно, я, соответственно, с этим фактом связываю надежду на (относительно) быстрое нахождение наименьших чисел, сваливающихся в единицу за $n$ утроений (обозначение $R_n^{\min}$ в тексте выше)

[Dmitriy40]

waxtep
Мне кажется Вы для уменьшения перебора существенно опираетесь на недоказанную эвристику.

Я сделал перебор по своему, рекурсивно вычисляю $m_i$ в порядке увеличения $i$, с ограничением всех промежуточных $r_i$ на каждом шаге (без эвристик, максимально полно, но не больше текущего минимума), но оказалось совсем непрактично, он относительно быстро уменьшает $r_n$ до где-то стократной истинной величины и потом затыкается во внутренних переборах $m_i$. Так что дождаться скажем $n=60$ ещё можно, а вот длиннее ...
У Вас же не затыкание переборов будет, а разрастание с каждым шагом списка допустимых векторов, что только хуже (медленнее). И даже эвристика начнёт сильно ограничивать количество вариантов векторов лишь ближе к концу (это видно и из Вашего примера, количество стало уменьшаться лишь с седьмого шага из девяти).

waxtep в сообщении #1618991 писал(а):

1) Алгоритм, запущенный для какого-то $n$, должен давать не только $R_n^{\min}$, но и все $R_k^{\min},k<n$

Неа, он точно не найдет $R_n^{\min}=0\pmod3$, как например в Вашем примере не нашёл $R_6^{\min}=9$. Конечно это можно вернуть, тогда думаю да, найдёт и меньшие.

[waxtep]

Dmitriy40 в сообщении #1618999 писал(а):

Мне кажется Вы для уменьшения перебора существенно опираетесь на недоказанную эвристику.

Конечно, без этого вообще безумные объемы вычислений. Алгоритм выдает псевдо-минимальные числа, строго говоря.

Dmitriy40 в сообщении #1618999 писал(а):

У Вас же не затыкание переборов будет, а разрастание с каждым шагом списка допустимых векторов, что только хуже (медленнее)

Есть такой риск; там будет борьба разрастания вариантов с сокращением, за счет модулярных соображений и эвристического ограничения на $s_n$

Dmitriy40 в сообщении #1618999 писал(а):

Неа, он точно не найдет $R_n^{\min}=0\pmod3$, как например в Вашем примере не нашёл $R_6^{\min}=9$. Конечно это можно вернуть, тогда думаю да, найдёт и меньшие.

Найдет-найдет, я же иду снизу вверх, посмотрите на $R_2$. Я просто дальше такие не выписываю, поскольку ясно, что число более высокого класса не свалится в делящееся на три низкого класса.

[Dmitriy40]

waxtep в сообщении #1619028 писал(а):

Я просто дальше такие не выписываю,

Ну я это и имел в виду, что если их не игнорить, то да, найдёт.

Но Вы понимаете что для меньших $n$ у Вас эвристика будет неправильной (слишком завышенной)? Она же для конечного $n$, а для меньших вариантов нужно меньше. Так что найдёт, но с огромным излишним (для меньших $n$) разрастанием списка векторов.

В общем способ (что Ваш, что мой) рабочий, но по моему всё же непрактичный. Разве что для $n>1000$ где-нибудь ... Куда линейным перебором за разумное время не добраться.

У меня счёт дошёл до 150e12, максимальное найденное $n=687$, минимальное не найденное $n=627$.

-- 21.11.2023, 12:00 --

waxtep в сообщении #1619028 писал(а):

Конечно, без этого вообще безумные объемы вычислений.

Ну, не всё так плохо: у меня почти моментально находится более-менее хорошее приближение сверху (вычисляю следующее $m_i$ как минимально допустимое при фиксированных предыдущих, для $n>70$ оно конечно улетает ввысь) и всё сваливается почти к той же эвристике (не точно, завышенно, зато без недоказанных предположений). Вот например динамика для $R_{40}=41$:

[4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]: Rn=10^99, s=4
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 2, 4, 4, 2, 1, 4, 4, 2, 2, 1, 2, 3, 4, 4, 4, 2, 4, 4, 4, 2, 4, 2]: Rn=5354753308337, s=106
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 2, 4, 4, 2, 1, 4, 4, 2, 2, 1, 2, 3, 4, 4, 4, 2, 4, 4, 4, 4, 1, 2]: Rn=2677376654169, s=105
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 2, 4, 4, 2, 1, 4, 4, 2, 2, 1, 2, 3, 4, 4, 4, 2, 4, 6, 1, 2, 2, 1]: Rn=334672081771, s=102
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 2, 4, 4, 2, 1, 4, 4, 2, 2, 1, 2, 3, 4, 4, 4, 2, 6, 3, 1, 1, 2, 1]: Rn=83668020443, s=100
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 2, 4, 4, 2, 1, 4, 4, 2, 2, 1, 2, 3, 4, 4, 4, 4, 1, 2, 1, 5, 1, 2]: Rn=83668020441, s=100
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 2, 4, 4, 2, 1, 4, 4, 2, 2, 1, 2, 3, 4, 4, 4, 4, 3, 1, 1, 1, 2, 1]: Rn=10458502555, s=97
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 2, 4, 4, 2, 1, 4, 4, 2, 2, 1, 2, 3, 4, 6, 1, 2, 2, 1, 1, 4, 2, 1]: Rn=5229251275, s=96
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 2, 4, 4, 2, 1, 4, 4, 2, 2, 1, 2, 3, 6, 3, 1, 1, 2, 5, 1, 1, 1, 2]: Rn=2614625641, s=95
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 2, 4, 4, 2, 1, 4, 4, 2, 2, 1, 2, 5, 1, 2, 1, 3, 4, 2, 2, 2, 2, 1]: Rn=1307312811, s=94
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 2, 4, 4, 2, 1, 4, 4, 2, 2, 1, 2, 5, 3, 1, 1, 1, 2, 3, 2, 2, 2, 1]: Rn=326828203, s=92
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 2, 4, 4, 2, 1, 4, 4, 2, 2, 1, 6, 2, 3, 1, 1, 2, 1, 2, 2, 1, 1, 1]: Rn=81707055, s=90
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 2, 4, 4, 2, 1, 4, 4, 2, 2, 3, 1, 1, 2, 1, 1, 4, 2, 1, 3, 1, 2, 2]: Rn=81707041, s=90
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 2, 4, 4, 2, 1, 4, 4, 2, 6, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1]: Rn=40853531, s=89
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 2, 4, 4, 2, 3, 1, 2, 3, 2, 1, 1, 3, 4, 2, 1, 1, 2, 2, 2, 2, 2, 2]: Rn=40853505, s=89
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 2, 4, 4, 2, 3, 1, 2, 5, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 1, 1, 1, 1]: Rn=319167, s=82
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 4, 1, 2, 3, 1, 1, 2, 1, 2, 5, 2, 1, 2, 1, 1, 2, 2, 3, 2, 1, 1, 1]: Rn=319151, s=82
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 4, 1, 2, 3, 1, 1, 2, 3, 1, 1, 1, 2, 1, 3, 4, 3, 1, 2, 1, 2, 1, 1]: Rn=319143, s=82
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 4, 2, 1, 4, 1, 2, 3, 1, 1, 2, 3, 1, 1, 3, 1, 1, 1, 2, 2, 1, 2, 1, 1, 1, 2]: Rn=19945, s=78
[4, 3, 2, 1, 1, 4, 2, 2, 1, 4, 2, 1, 3, 2, 2, 6, 1, 3, 2, 1, 2, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2]: Rn=4985, s=76
[4, 3, 2, 1, 3, 1, 4, 1, 2, 1, 3, 2, 1, 2, 5, 3, 3, 6, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1]: Rn=2559, s=75
[4, 5, 1, 1, 3, 4, 2, 2, 4, 1, 1, 1, 1, 2, 1, 1, 1, 3, 4, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 3, 1, 1, 1, 1, 4, 1, 2, 1, 1, 1]: Rn=1391, s=74
[4, 5, 1, 1, 3, 4, 2, 2, 4, 1, 1, 1, 3, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 1, 1, 2]: Rn=41, s=69
n=40: Rn=41
Time: 1,653 ms

Но $R_{50}=731$ находится уже лишь за 44с. $R_{54}=1145$ за 99с. А $R_{60}=1583$ за 352с. Но если считать $n$ подряд, то для $R_{60}$ можно взять начальное ограничение не $10^{99}$, а $16R_{59}/3+1\approx6500$ (с запасом), в таком случае время будет 342с - 95% тратится на большие $m_i$ с малым $i$, для них ограничения оказываются слишком мягкими.
Верхний индекс указывать откровенно влом, ведь интересуют только с $\min$ и никакие другие.
Правда я тоже сжульничал: насильно установил $m_1=4$ и перебираю только следующие.

[waxtep]

Dmitriy40 в сообщении #1619035 писал(а):

, в таком случае время будет 342с - 95% тратится на большие $m_i$ с малым $i$, для них ограничения оказываются слишком мягкими.

Да, я подумал, что видимо еще жульничать придется - ограничивать не только сумму $m_i$, но и величину каждого $ m_i$ в отдельности. Помню, Вы в самой первой статистике анализировали, для какого $n$ впервые появляется следующее по величине $m_i$. Возможно, здесь тоже есть какая-то приближенная закономерность, имеет смысл посмотреть.

-- 21.11.2023, 12:55 --

Dmitriy40 в сообщении #1617685 писал(а):

4. До $n=503$ встретились варианты $m_i\in\{1,2,3,4,5,6,7,8,9,10,12,15\}$, первое $m_i=10$ для $R_{197}=1501353$, первое $m_i=12$ для $R_{348}=1224961663$, первое (и пока единственное) $m_i=15$ для $R_{502}=1210271371431$.

Вот это

[Dmitriy40]

waxtep в сообщении #1619044 писал(а):

Да, я подумал, что видимо еще жульничать придется - ограничивать не только сумму $m_i$, но и величину каждого $ m_i$ в отдельности.

Так у меня практически так и делается: при обновлении рекорда $R_n$ я обновляю максимально допустимые промежуточные $r_{i<n}$, т.е. фактически $m_i$. Но чтобы не упираться в недоказанные эвристики беру $r_{i-1}=\lceil(3r_i+1)/2\rceil$ (реальное ограничение на $m_i$ при этом зависит от $m_{j<i}$ с меньшими индексами).
Дополнительное ручное ограничение $m_i<15$ эффекта не даёт: для $R_{54}=1145$ время уменьшается на жалкие 1.5с, меньше 2%.

-- 21.11.2023, 13:31 --

Вообще надо конечно поизучать в чём конкретно тормоза кода на PARI, а то окажется как обычно в самом PARI и переписывание на нормальном языке даст ускорение на пару-тройку порядков ...

[MGM]

waxtep в сообщении #1617495 писал(а):

Кажется, это что-то сезонное, по крайней мере я тоже маньячу в указанную гипотезу пару недель, независимо от появившихся недавно тем.
Не стал присоединяться к теме уважаемого Dmitriy40, поскольку интересуюсь частным вопросом: для данного натурального $n$ можно ли "легко" построить (хоть какое-то) натуральное нечетное $R_n$, которое "свалится в единицу" ровно за $n$ утроений? Далее попробую уточнить.

Задача тривиальная. Если нужно найти просто любое число с таким критерием (даже если остановить число умножений строго на первой единице). Таких чисел для любого $n $ бесконечное множество. Стройте обратное дерево от единицы. Более того, уже для $n=1$ чисел бесконечное множество.
$R_m^1 = \sum\limits_{i = 0}^m {{2^{2i}}} $
И каждые два числа из трех на уровне $R_m^n $ порождает бесконечное число чисел на уровне $ n+1$.
С минимальным числом - даже алгритм вряд ли сущесвует, не говоря уже об вменяемой аналитической формулы.
И все из-за тупиковых ветвей: если $R_m^n \equiv 0\bmod 3$ то это число - тупиковая ветвь.

PS Не совсем понятно, что вы хотите доказать в конце концов? Даже, допустим, если вы получите некоторою формулу типа:
$R_{\min }^n = f\left( n \right)$

[Dmitriy40]

Ну, тут осталось два вопроса:
1. Все ли минимальные $R_n$ приходят к единице с последним шагом $5\to1$, т.е. имеют $m_1=4$ или есть и другие. Менее интересно есть другие варианты четвёрок $(m_4,m_3,m_2,m_1)$ кроме $(1,2,3,4),(1,1,5,4),(5,1,5,4)$. Я до 150e12 других не обнаружил.
2. Как вычислять $R_n^{\min}$ без полного перебора всех (или очень и очень многих, пока лишь с ограничениями $2R_n/3 < R_{n+1} < 16R_n/3+1$) нечётных. На данный момент шлифуем метод рекурсии с возвратом (я) и итерационного построения множества допустимых векторов $m_i$ на каждом шаге $j=1\ldots n$ (waxtep). По моему и тот и другой способы непрактичны, невзирая на все эвристики.

Процитированный вопрос, построение любого $R_n$, не обязательно минимального, несложен - поднятие по дереву с вычислением минимально подходящего $m_i$, но числа $R_n$ получаются на много (десятки!) порядков больше минимальных. Для них даже оценка приведена, по эвристике, но всё же.

[MGM]

Нет, конечно. 5ка, как порождающий элемент обратного дерева - конечно очень важная вершина, но вот уже число 85 сразу валится к единице. Бинарный делитель 256.

$85 \times 3 + 1 = 256 = {2^8}$
А первое число от 85ти на уровне выше вычисляется:
$\frac{{85 \times 4 - 1}}{3} = 113$
То есть 113 - это число в двух шагах от единицы и проходит не через 5, а через 85.
Но среди чисел второго уровня все же минимальное 3. И тройка сваливается к единице через 5ку.

[waxtep]

Сделал прототипчик, но да, считает очень долго, уже для $n=41$ у меня терпения не хватило. Отчасти, возможно, из-за возни с матрицами, но, факт, число вариантов растет слишком быстро. Надо еще думать, значит.
cz_eur(n)={my(sn=ceil(5*n/3)+7,px=floor((sn-n-3)/2)+1,Rcurr=matrix(px,3,p,col,(vectorv(px,v,1)*[(2^(4+2*(p-1))-1)/3,4+2*(p-1),4+2*(p-1)])[p,col]),Rnext=vector(4),R,s,m,ma,un);
for(i=2,n,
a=matsize(Rcurr)[1];
printp(vecmin(Rcurr[1..a,1]));
\\printp(Rcurr);
for(j=1,a,
R=Rcurr[j,1];
s=Rcurr[j,2];
m=Rcurr[j,3..i+1];
if(Mod(R,3)==1,px=floor((sn-s-n+i)/2);if(px>=1,ma=vectorv(px,k,2*k);un=vectorv(px,v,1);Rnext=matconcat([Rnext;matconcat([round((2^ma*R-un)/3),un*s+ma,un*m,ma])])));
if(Mod(R,3)==2,px=ceil((sn-s-n+i)/2);if(px>=1,ma=vectorv(px,k,2*k-1);un=vectorv(px,v,1);Rnext=matconcat([Rnext;matconcat([round((2^ma*R-un)/3),un*s+ma,un*m,ma])])));
);
Rcurr=Rnext[2..matsize(Rnext)[1],1..i+2];
Rnext=vector(i+3);
);
a=matsize(Rcurr)[1];
printp(vecmin(Rcurr[1..a,1]));
\\printp(Rcurr);
};

-- 21.11.2023, 19:55 --

MGM в сообщении #1619146 писал(а):

Но среди чисел второго уровня все же минимальное 3. И тройка сваливается к единице через 5ку.

В этом и вопрос: все ли минимальные сваливаются в единицу через пятерку?

[MGM]

waxtep в сообщении #1619147 писал(а):

MGM в сообщении #1619146 писал(а):

Но среди чисел второго уровня все же минимальное 3. И тройка сваливается к единице через 5ку.

В этом и вопрос: все ли минимальные сваливаются в единицу через пятерку?

Не думаю. Для достаточно больших чисел ($n=2^{1000}$, например ) скорее всего не так.
Но можете попробовать доказать следущее:
${m_1} = \mathop {\arg \min }\limits_{\left\{ {{m_1},{m_2},..{m_n}} \right\}} \left( {\frac{{{2^{{m_n}}} - {3^{n - 1}} - {3^{n - 2}}{2^{{m_1}}} - {3^{n - 3}}{2^{{m_2}}}... - {2^{{m_{n - 1}}}}}}{{{3^n}}}} \right) = 2$

где ${m_k} < {m_{k + 1}}$
Так как степень при двойке возрастает, а степень при тройке убывает, то не факт, что такое можно доказать.

[Dmitriy40]

Моя программа, если захотите поиграться:

{Calc(n,i,rn)=my(x,y);\\rn - накопленное r по m[j<i]
   for(x=1,oo,\\цикл подбора m[i]
      y=rn*2^x-1;
      if(y>3*r[i], return);\\m[i] слишком велико
      if(y%3>0, next);\\m[i] не подходит, число не целое
      m[i]=x; y=y/3;
      if(i<n,
         if(y%3>0, Calc(n,i+1,y));\\внутри кратное трём недопустимо
      ,
         if(y>=r[n], next);\\m[n] слишком велико, нового меньшего Rn нет
         r[n]=y; forstep(y=n-1,1,-1, r[y]=ceil((3*r[y+1]+1)/2));\\пересчёт r[i] в обратном порядке от нового Rn=r[n]
         print(m,": R=",y,", s=",vecsum(m));\\показ процесса уменьшения Rn
      );
   );
}

n=40;
m=vector(n); r=vector(#m,i,3^n+100); m[1]=4;
print(m,": R=",r[n]);
Calc(n,2,(2^m[1]-1)/3);\\i=1 уже вычислено насильно
print("n=",n,": Rn=",r[n]);