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

[Dmitriy40]

Чтобы не быть голословным, вот код обоих циклов (по нечётному числу в R15 и вычисления по нему $n$ в R10) до оптимизаций и проверок:

Используется синтаксис ASM

        mov     R15,3-2         ;x0-2
.x0:    add     R15,2           ;x0=x0+2
        mov     R10,0           ;n=0
        mov     RAX,R15         ;x=x0
        mov     R11,0           ;xh=0
.x:     inc     R10             ;n++
        mov     R9,R11
        mov     R8,RAX
        add     R8,R8
        adc     R9,R9           ;R9R8=2x
        inc     R8              ;R9R8=2x+1
        add     RAX,R8
        adc     R11,R9          ;R11RAX=3x+1
        bsf     RCX,RAX
        shrd    RAX,R11,CL
        shr     R11,CL          ;R11RAX=(3x+1)>>k
        jnz     .x              ;x>=2^64?
        cmp     RAX,1
        jne     .x
        mov     RAX,[Rn+R10*8]
        test    RAX,RAX
        jne     .x0             ;такое n уже известно?
        mov     [Rn+R10*8],R15  ;нет, сохраним найденное
        stdcall Disp, R10, R15  ;печать нового n=R10, Rn=x0=R15
        jmp     .x0

Цикл расчёта $n$ начинается меткой .x и заканчивается jne .x0.
Можете сравнить со своим любимым компилятором.

-- Ср ноя 22, 2023 20:21:20 --

Выше есть небольшая ошибка, возникающая если некоторое $m_i>63$, что впрочем для наших чисел похоже пока не случается. К тому же в рабочем коде она исправлена.

[waxtep]

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

Если используется в цикле, то проще сразу выделить вектор/матрицу с большим запасом, в цикле заполнить, а по выходу обрезать (m=m[1..n]) до нужного размера, только это запросто даст ускорение до порядка.

В общем, вот такой вот крокодилиум (отказался от конкатов и ввернул еще два внутренних цикла) действительно работает еще на порядок-другой быстрее:

(код)

cz_eur(n)={my(sn=ceil(5*n/3)+7,px=floor((sn-n-3)/2)+1,
Rcurr=matrix(1,3,i,j,[1,0,px][j]),
Rnext=matrix(px,4),
spx=0,k0=1,
R,s,m,ma,un);
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]));

   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,
            rnk=(R<<(2*k+f)-1)/3; rnkm=rnk%3;
            mk=2*k+f;
            snk=s+mk;
            dspx=if(rnkm==1,floor((sn-snk-n+i+1)/2),
                  rnkm==2,ceil((sn-snk-n+i+1)/2),
                  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=49$ он считал 6 минут, с максимальным количеством в $583445$ вариантов на $18$-ом шаге.

-- 22.11.2023, 20:33 --

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

Про 5ку. Если нечетное число минимальное для всех других чисел этого уровня $R_n^{\min }$
То 5ка всегда элемент последовательности.
Что следует из вот этого легко доказуемого утверждения:
${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$
Оно верно, если преобразовать выражение в скобке, то это уже очевидно.
$\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}}} = \frac{{{2^{{m_1}}}\left( {{2^{{m_n} - {m_1}}} - {3^{n - 2}} - {3^{n - 3}}{2^{{m_2} - {m_1}}}... - {2^{{m_{n - 1}} - {m_1}}}} \right)}}{{{3^n}}} - \frac{1}{3}$
Если непонятно, спросите профессиональных математиков. Если такие есть в вашем окружении.

У Вас несколько другие обозначения, в частности, Ваше $m_1^{MGM}=m_n$ в обозначениях, принятых в топике. Действительно, очевидно, что $m_1^{MGM}$ это единица или двойка для минимальных чисел. Пользуясь Вашими обозначениями, вопрос топика звучит так: верно ли, что для минимальных нечетных сваливающихся в единицу за $n$ утроений, всегда $m_n^{MGM}-m_{n-1}^{MGM}=4$?

[MGM]

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

Интересное наблюдение: чтобы найти все $n<603$ достаточно перебрать нечётные числа до 50e12, а вот если каждое следующее $R_n$ искать относительно предыдущего (начиная с $2/3$ от него), то перебрать придётся 460e12, в девять раз больше! Т.е. без существенных оптимизаций (исключающих перекрытие интервалов счёта) итерационный процесс на порядок проигрывает линейному.

Удивительно. Я даже не представляю, как можно организовать предел по $n$.
Так как, например, для числа $\frac{{k\frac{{{2^{1000000!}} - 1}}{3} - 1}}{3}$, где $k \in \left\{ {2,4,\emptyset } \right\}$, n=2.
Онако ни один компьютер не способен такое число даже записать, пользуясь стандартым компилятором учитывая, что 100000! это порядка 6 миллионов десятичных знаков.
Значит ваш алгоритм должен быть достаточно своеобразным, мягко говоря.

[Dmitriy40]

MGM
Вы упорно игнорируете что нас в этой теме интересуют исключительно наименьшие $R_n$ для каждого конкретного $n$. Например это вот ваше длинное число - не интересует, потому что для $n=2$ наименьшее $R_{n=2}=3$ и никакие большие него не интересны. А для $n=602$ наименьшее число сваливающееся в $1$ ровно за $n=602$ утроений есть $R_{n=602}=27667550250351$. И никакие числа больше этих для данных $n$ нас не интересуют!
Так что до 50e12 встретились числа, сваливающиеся к единице ровно за все $n=1\ldots602$. Для некоторых $n$ и не по одному разу встретились, но нас интересуют только наименьшие для каждого $n$. А вот числа сваливающегося в единицу за $n=603$ утроений не встретилось. Зато встретились $R_{608}, R_{616}$.

-- 22.11.2023, 21:44 --

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

Онако ни один компьютер не способен такое число даже записать, пользуясь стандартым компилятором учитывая, что 100000! это порядка 6 миллионов десятичных знаков.

PARI/GP с такими числами работает вполне себе легко (но медленно), как и с любыми другими. За что и любим.

[MGM]

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

У Вас несколько другие обозначения, в частности, Ваше $m_1^{MGM}=m_n$ в обозначениях, принятых в топике. Действительно, очевидно, что $m_1^{MGM}$ это единица или двойка для минимальных чисел. Пользуясь Вашими обозначениями, вопрос топика звучит так: верно ли, что для минимальных нечетных сваливающихся в единицу за $n$ утроений, всегда $m_n^{MGM}-m_{n-1}^{MGM}=4$?

$m_1$ у меня это степень первого делителя до единицы.

$m_n$ - степень кумулятивного делителя. ${m_2} = {m_1} + {k_2} $ То есть суммарный по логарифму двойки.
Но на свежий глаз я понял, что доказательство неверное. Забудьте. Первоначальная идея была вынести $m_1$ за скобки, и типа минимум зависит только от множителя. А минимальный он при $m_1$ = 4. Что в целом неверно. Я уже делал такие ляпы, когда посчитал, что минимум для разницы степеней двойки и тройки $\left| {{3^} - {2^n}} \right|$ стремится к бесконечности при стремлении одной из степеней. Как-то не удалось это доказать.

-- Ср ноя 22, 2023 23:09:16 --

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

MGM
Вы упорно игнорируете что нас в этой теме интересуют исключительно наименьшие $R_n$ для каждого конкретного $n$. Например это вот ваше длинное число - не интересует, потому что для $n=2$ наименьшее $R_{n=2}=3$ и никакие большие него не интересны. А для $n=602$ наименьшее число сваливающееся в $1$ ровно за $n=602$ утроений есть $R_{n=602}=27667550250351$. И никакие числа больше этих для данных $n$ нас не интересуют!
Так что до 50e12 встретились числа, сваливающиеся к единице ровно за все $n=1\ldots602$. Для некоторых $n$ и не по одному разу встретились, но нас интересуют только наименьшие для каждого $n$. А вот числа сваливающегося в единицу за $n=603$ утроений не встретилось. Зато встретились $R_{608}, R_{616}$.

Я понимаю, что вас интересует. Однако вы должны организовать алгоритм так, что бы перебирать какие-то нечетные числа с известной границей.
То есть вы утверждаете, что у вас есть формула, типа этой?
$R_n^{\min } < f\left( n \right)$
Поздравляю.
Буду премного благодарен, если увижу такую формулу.
Если это алгоритм - то у него так же должны быть базовые формулы. Но это уже менее интересно.


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

[waxtep]

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

$m_1$ у меня это степень первого делителя до единицы.

Ну, в Вашей формуле, $2^{m_1}$ - это коэффициент перед $3^{n-2}$ - значит, это показатель первого делителя считая от $R_n$. Нас здесь интересует другой, - последний считая от $R_n$, и первый от единицы. Это разность двух кумулятивных показателей в Ваших обозначениях. Вот как-то он всегда четверка для минимальных чисел, пока что. Впрочем, раз доказательства нет, не важно.

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

То есть вы утверждаете, что у вас есть формула, типа этой?
$R_n^{\min } < f\left( n \right)$
Поздравляю.

Есть доказанные нижняя и верхняя граница, гляньте на второй странице топика.

[Dmitriy40]

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

Однако вы должны организовать алгоритм так, что бы перебирать какие-то нечетные числа с известной границей.

Зачем? Не должен. Просто перебираю все нечётные в порядке возрастания и если обнаруживаю что какое-то из них приходит к единице за количество шагов, за которое до этого ни одно меньшее не приходило - значит это новое значение $n$ и $R_n$. Записываю и продолжаю. Никакой границы нет.

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

То есть вы утверждаете, что у вас есть формула, типа этой?

Формулы нет (ограничение сверху непрактично), зато есть список найденных значений. А раз он полный (т.е. без пропусков) вплоть до $n=626$, то делаю вывод что все такие $n$ (и $R_n$ разумеется) найдены до некоторого числа (134e12). Но могу конечно и задать таблично такую функцию, но лишь для $n<627$, других её значений (за 8-ю исключениями) мне пока неизвестно.

В итоге я не понимаю чего Вы от меня хотите. Или в чём сомневаетесь.

-- 22.11.2023, 23:07 --

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

В первый раз вижу любителей Сиракузской поселедовательности, которых итересуют минимумы, а не максимумы.

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

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

Еще чуть добавлю: вот минимальные $R_n$: A092893;

Там указаны 300 элементов (до 276e6, странно что не показали 301-306, они все меньше 230e6), я досчитал следующие 326 (до 200e12).

-- 22.11.2023, 23:37 --

MGM
Слушайте, может Вам код на C более понятен будет?

Используется синтаксис C

int Rn[3000];//Известный рекорд всего 2441
for(R=3; ; R+=2) {
        x=R; n=0; while(x>1) { ++n; x=3*x+1; while((x&1)==0) { x>>=1; } }//Вычисление n для данного R
        if(Rn[n]==0) { Rn[n]=R; printf("n=%u: Rn=%u\n", n,R); }//Если такого n ещё не встретилось, то запоминаем и печатаем
}

[MGM]

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

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

Однако вы должны организовать алгоритм так, что бы перебирать какие-то нечетные числа с известной границей.

Зачем? Не должен. Просто перебираю все нечётные в порядке возрастания и если обнаруживаю что какое-то из них приходит к единице за количество шагов, за которое до этого ни одно меньшее не приходило - значит это новое значение $n$ и $R_n$. Записываю и продолжаю. Никакой границы нет.



В итоге я не понимаю чего Вы от меня хотите. Или в чём сомневаетесь.

-- 22.11.2023, 23:07 --

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

В первый раз вижу любителей Сиракузской поселедовательности, которых итересуют минимумы, а не максимумы.

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

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

Еще чуть добавлю: вот минимальные $R_n$: A092893;

Там указаны 300 элементов (до 276e6, странно что не показали 301-306, они все меньше 230e6), я досчитал следующие 326 (до 200e12).

-- 22.11.2023, 23:37 --

MGM
Слушайте, может Вам код на C более понятен будет?

Используется синтаксис C

int Rn[3000];//Известный рекорд всего 2441
for(R=3; ; R+=2) {
        x=R; n=0; while(x>1) { ++n; x=3*x+1; while((x&1)==0) { x>>=1; } }//Вычисление n для данного R
        if(Rn[n]==0) { Rn[n]=R; printf("n=%u: Rn=%u\n", n,R); }//Если такого n ещё не встретилось, то запоминаем и печатаем
}

Понятно. Значит моя надежда, что вы зацепили какой-то особый алгорим обратного дерева не оправдалась.
Что касается перебора, я таких программ могу выдать дюжину за час.
Однако теперь мне понятно, как вы решаете эту проблему. Логично. Старею.
Остался только один вопрос, чисто из любопытсва, если при переборе сначала вы получаете 300 шагов, а затем сразу 700?
Какие ваши действия? И были ли такие случаи?

[Dmitriy40]

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

Значит моя надежда, что вы зацепили какой-то особый алгорим обратного дерева не оправдалась.

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

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

Остался только один вопрос, чисто из любопытсва, если при переборе сначала вы получаете 300 шагов, а затем сразу 700?
Какие ваши действия? И были ли такие случаи?

Случаи разумеется были, полным полно, скорее обратное - исключения. Пример: найдены все $n<627$, и например $n=683,685,686,687$. Действия - видны в исходнике на С - сохраняю в массив чтобы больше числа с таким $n$ не учитывать (это и обеспечивает минимальность) и печатаю в консоль. Сортировку и проверку на непрерывность списка $n$ не показал, это можно и руками сделать. Не вижу ничего странного или особенного в вычислении $n$ не подряд.

-- 23.11.2023, 02:47 --

Ну вернее 300 и сразу 700 конечно не было - 700 вообще не было. Но большая разница была, да. Например 542 и тут же 583. Или 275 и тут же 357. Или 604 и почти сразу 686.
Но никакой проблемы в этом нет.

[MGM]

А какое отноношение ваши эксзерзисы имеют к гипотезе Коллатца?
Собственно про пятерку, как уникальнуную вершину, это скорее ваша гипотеза.
И вообще, я бы назвал тему внутри Сиракузской последовательности. Никакой попытки доказать гипотезу Коллатца я не вижу.


PS Если бы вы создали аналитический алгоритм достижения минимума для шага n с помощью обратного дерева, то это был бы реальный шаг к доказательству именно гипотезы Коллатца.

[Утундрий]

Можно некоторое резюме для тех, кто смотрит с самого начала, но до сих пор ничего не понимает?

[Dmitriy40]

MGM
Во-первых ТС не я и тему называл тоже не я.
Во-вторых, про 5 гипотеза тоже не моя, а ТС.
В-третьих, кажется тут про доказательство именно гипотезы Колатца речи и не шло изначально. Просто некоторые родственные аспекты. И название "гипотеза Колатца" более широко известно народу чем "Сиракузская последовательность", не вижу в этом ничего сильно плохого. Нет, конечно, если бы оценка снизу для $R_n$ при некоем $n$ уходила бы строго в бесконечность это и стало бы доказательством, но такое получить очевидно невозможно (обратное дерево ни для какого $n$ не уходит в бесконечность, для $R_n$ есть верхняя оценка от $n$). Конечность обратного дерева из единицы не является доказательством гипотезы Колатца потому что не учитывает возможное наличие других циклов кроме $4\to3\to1\to4$. А доказать что обратное дерево из единицы покрывает все нечётные числа (и соответственно других циклов нет) никому не удалось (и мы тут этим не занимаемся).

Утундрий
Есть A092893, вопросов у ТС по ней два (насколько я понимаю происходящее):
1. Можно ли получать её члены кроме как полным перебором всех нечётных чисел? Ответ - да, можно, обратным ходом от 1 вверх, но сильно непрактично по сравнению с перебором всех нечётных. Вопрос можно ли улучшить или придумать что-то ещё.
2. Все ли её члены приходят к 1 через 5? Пока из найденных 634 членов (до 200e12) - все.
Было ещё несколько попутных вопросов, например про оценку следующего её члена от предыдущего, но это частности в рамках первого вопроса.

[MGM]

Обратное дерево уходит в бесконечность. Проблема в плотности. Все ли числа можно представить в виде обратного дерева.

[Dmitriy40]

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

Обратное дерево уходит в бесконечность.

При $n\to\infty$ или если брать любое подходящее число (не именно минимальное), при любом конечном $n$ обратное дерево до минимального подходящего числа ограничено сверху (а вся эта тема - про такие числа, минимальные, уже в который раз повторяю).

[Утундрий]

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

Есть A092893

Интересно, что там делает $5$? Первая же итерация приводит к степени двойки, следовательно $5$ не содержит ни одного "тройного шага" и не перебивает $1$.