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

[Dmitriy40]

Оказывается я занимаюсь ерундой: из https://oeis.org/A033491/b033491.txt простой программкой легко получаются все $n<724$ до $10^{16}$, мне дотуда считать месяцев 8 ... Программка:

v=readstr("b033491.txt"); q=vector(#v);
foreach(v,s, x0=eval(strsplit(s," ")[2]); if(x0%2==0 || x0<3, next); x=x0;n=0; while(x>1, n++; x=3*x+1; x>>=valuation(x,2); ); if(q[n]==0 || x0<q[n], q[n]=x0; ); );
for(n=1,#q, if(q[n]>0, print("n=",n,": Rn=",q[n])); );

Но зато я проверил все $R_n$ какие только смог найти, например отсюда и отсюда, все проходят через $5$ ($m_1=4$).

[waxtep]

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

Оказывается я занимаюсь ерундой: из https://oeis.org/A033491/b033491.txt простой программкой легко получаются все $n<724$ до $10^{16}$, мне дотуда считать месяцев 8

Это чит Получается, кто-то просто уже перебрал дотуда, и тоже видимо небыстро, а Вы проверяете. Я подумал, наверное, все таки, $m_1=4$ рулит: ведь следующее возможное $m_1=8$, и ммм я затрудняюсь это внятно выразить, но наверняка можно сделать "хвост" почти в $2^{8-4}=16$ раз больше, и тем не менее получить меньшее число с $m_1=4$. Как-то можно попробовать это формализовать

[Dmitriy40]

Хм, всё даже хуже лучше чем я думал выше: по второй приведённой ссылке есть полные данные и до $n \le 770$, а это уже до 6.5e16 или более 4 лет счёта мне. Столько времени жаль, так что досчитаю к вечеру до 288e12 (найдутся ещё три значения) и остановлю.

[waxtep]

Я тем временем еще немного повозился со своим "деревянным" алгоритмом, в нем можно достичь значительных успехов, потребовав не только глобального соответствия эвристике $s_n\leqslant\lceil{5n/3}\rceil+7$, но и локального соответствия более мягкой типа $s_k\leqslant\lceil{5k/3}\rceil+17$. Например, кусок кода ниже, за пару минут правильно посчитает все минимальные $R_n, n\leqslant108$:

(код)

cz_eurzh1(n)={my(sn=ceil(5*n/3)+7,px=9,
Rcurr=matrix(1,3,i,j,[1,0,px][j]),
Rnext=matrix(px,4),
spx=0,k0=1,
R,s,m,rnk,rnkm,mk,snk,dspx,kin,her);
printp(["n","R_min","R_max","#","m_max"]);
for(i=1,n,
a=matsize(Rcurr)[1];
if(i>1,printp([i-1,vecmin(Rcurr[1..a,1]),vecmax(Rcurr[1..a,1]),a,vecmax(Rcurr[1..a,4..i+2])])
,printp([i-1,vecmin(Rcurr[1..a,1]),vecmax(Rcurr[1..a,1]),a]));
\\if(i>=107,printp(Rcurr));

for(j=1,a,
R=Rcurr[j,1];
s=Rcurr[j,2];
px=Rcurr[j,3];
if(i>1,m=Rcurr[j,4..i+2]);

if(px>=1,
if(i==1,f=2,f=1-R%3);
for(k=1,px,
mk=2*k+f;
rnk=(R<<mk-1)/3; rnkm=rnk%3;
snk=s+mk;
her=5+ceil((ceil(5*(i+1)/3)+7-snk)/2);
\\if(i>=45,her=her+2);
\\if(i>=50,her=her-1);
\\if(i>=67,her=her-1);
dspx=if(rnkm==1,min(floor((sn-snk-n+i+1)/2),her),
rnkm==2,min(ceil((sn-snk-n+i+1)/2),her),
rnkm==0,0);
if(dspx>0,spx=spx+dspx);
kin=k+k0-1;
Rnext[kin,1]=rnk;
Rnext[kin,2]=snk;
Rnext[kin,3]=dspx;
Rnext[kin,i+3]=mk;
if(i>1,for(v=4,i+2,Rnext[kin,v]=m[v-3]));
);
k0=k0+px;
);
);
Rcurr=Rnext;
\\printp(Rcurr);
Rnext=matrix(spx,i+4);
spx=0;
k0=1;
);

a=matsize(Rcurr)[1];
printp([n,vecmin(Rcurr[1..a,1]),vecmax(Rcurr[1..a,1]),a,vecmax(Rcurr[1..a,4..n+3])]);
printp(Rcurr);
};

А если раскомментировать жульнический кусок кода (опирающийся на известный результат для $n=109$)
if(i>=45,her=her+2);
if(i>=50,her=her-1);
if(i>=67,her=her-1);
во внутреннем цикле (позволяющий иногда $m_k$ быть побольше), то так же за минуты правильно посчитает и многие (не все) минимальные $R_n,109\leqslant{n}\leqslant183$, а начиная с $n=184$ уже окончательно пойдет вразнос.
Проблема, конечно, в том, как определить, когда именно требуется ослабить локальное ограничение, а когда снова можно установить его построже, это непонятно

[MGM]

баг

[MGM]

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

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

Оказывается я занимаюсь ерундой: из https://oeis.org/A033491/b033491.txt простой программкой легко получаются все $n<724$ до $10^{16}$, мне дотуда считать месяцев 8

Это чит Получается, кто-то просто уже перебрал дотуда, и тоже видимо небыстро, а Вы проверяете. Я подумал, наверное, все таки, $m_1=4$ рулит: ведь следующее возможное $m_1=8$, и ммм я затрудняюсь это внятно выразить, но наверняка можно сделать "хвост" почти в $2^{8-4}=16$ раз больше, и тем не менее получить меньшее число с $m_1=4$. Как-то можно попробовать это формализовать

Вы сначала формализуйте все значения для $m_1$. Это просто.
$m_1$ = {4,6,8,10..}. Потом выкидываете каждую третью вершину, начиная с 6. Так как это тупиковая вершина ветвления для первого уровня.
Но по ходу, скорее всего доказать, что 4ка - единственная вершина ветвления для минимума не просто. Я уже записывал формальное условие. Как бы для первых уровней глубины это доказать можно. И легко, а дальше - индукция. Но очень и очень нетривиальная. Во всяком случае эта задача очень-очень похожа на доказательство отсутсвия нетривиальных циклов в Сиракузской последовательности.

[waxtep]

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

Проблема, конечно, в том, как определить, когда именно требуется ослабить локальное ограничение, а когда снова можно установить его построже, это непонятно

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

$$R_n=\frac1{3^n}\left(2^{\sum\limits_{i=1}^{n}{m_i}}-\sum\limits_{i=2}^{n+1}{3^{i-2}\cdot2^{\sum\limits_{j=i}^n{m_j}}}}\right)$$

и сделать следующие два предположения для минимальных $R_n$:
1) В составе минимального $R_n$ совсем немного $m_i$, не являющихся минимальными подходящими ("кости"); основную же массу составляет минимально подходящее "мясо" из $m_i\leqslant4$
2) Искать "кости" можно слева направо по одной, заполняя все справа от "кости" "мясом"; при этом, любая установка значения кандидата в "кости" должна приводить к уменьшению суммы $m_i$ (дальше ее обозначаю как $s$).
Первое предположение по всей видимости выполняется, а второе точно не всегда.

Попробую проиллюстрировать, как это выглядит, для $n=57$:
0) сначала строим $R_{57}$ только из мяса и получаем $s=141$;
1) добавляем первую кость $m_2=5$ и получаем $s=132$;
2) теперь $m_9=4\Rightarrow s=120$;
3) $m_{13}=3\Rightarrow s=111$;
4) $m_{43}=4\Rightarrow s=105$;
5) $m_{46}=4\Rightarrow s=101$ дает минимальное $R_{57}=1351$.
На каждом шаге $s$ уменьшается и все прекрасно работает. Это по сути "жадная" версия рекурсивного алгоритма с очень ограниченным ветвлением (в данном примере на каждом из первых четырех шагов есть еще несколько "паразитных" веток - $2,1,2,5$ соответственно; код не привожу - все равно не работает).

Но вот например для $n=109$ "мясорубка" ломается сразу же, поскольку добавление первой "настоящей" кости (действительно входящей в состав минимального $R_{109}=64255$) $m_5=3$ в скелет приводит не к уменьшению, а к увеличению $s$ с $255$ до $268$. Вместе с надеждой существенно ограничить ветвление, эх. Остается только анатомическое представление минимальных $R_n$, если не полезное, то хотя бы живописное