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

[MGM]

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

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

Спасибо, конечно, но если вы посмотрите на мою формулу, то её доказательство очевидно.
Так что ваша гипотеза верна. На 100%. Если кому-то не очевидно, поупражняетесь в алгебре.
В брагодарность жду от вас разъяснений, чему это вообще может помочь. :)

[Dmitriy40]

MGM
Да я собственно для waxtep программу то ...

А формулу Вашу не понимаю в упор. Не то что вычленить из неё доказательство $m_1=4$.

[MGM]

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

MGM
Да я собственно для waxtep программу то ...

формулу Вашу не понимаю в упор. Не то что вычленить из неё доказательство $m_1=4$.

У меня $m_1=2$ так как это степень двойки. Но не суть.
Просто поверьте на слово. То, что в скобках - представление произвольного нечетного, достигающего единицы после n умножений на 3.
При $m_1=2$ это выражение в скобках достигает минимума.


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

[Dmitriy40]

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

У меня $m_1=2$ так как это степень двойки. Но не суть.

У нас тоже: $5 \to 16 \to 1$, последний переход и отражает что $16=2^{m_1=4}$.

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

При $m_1=2$ это выражение в скобках достигает минимума.

Прелестно. Тогда почему же мы не видим $m_1\ne4$? Одни только $m_1=4$ ... Наверное важен не только минимум ...

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

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

А и выдайте: какое минимальное число, из всех приходящих в $1$ за ровно $n$ утроений, проходит в конце не через $5\to1$. Не абы какое из приходящих в $1$ за ровно $n$ утроений, а строго минимальное. Вот до $n=627$ таковых точно нет (до $n=602$ я показывал их все выше), ну так приведите с большим значением $n$.
И если что, то это не моя гипотеза, а waxtep-а.

[waxtep]

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

Дополнительное ручное ограничение $m_i<15$ эффекта не даёт: для $R_{54}=1145$ время уменьшается на жалкие 1.5с, меньше 2%.

Вы правы, это ничего существенного не дает, по крайней мере для малых $n$, с которыми я сейчас возюкаюсь, чтобы, так сказать, почувствовать, как оно работает

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

Вообще надо конечно поизучать в чём конкретно тормоза кода на PARI

У меня это видимо два в степени вектор (как поэлементная операция), PARI сразу встает на дыбы и переводит в тип с плавающей точкой; я там поэтому результат в round() обернул. А << для вектора не сделаешь, ошибка несоответствия типов. Я-то привык к Matlab-у, где возня с матрицами всегда существенно быстрее ручного цикла, а тут видимо необязательно так.

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

А и выдайте: какое минимальное число, из всех приходящих в $1$ за ровно $n$ утроений, проходит в конце не через $5\to1$. Не абы какое из приходящих в $1$ за ровно $n$ утроений, а строго минимальное. Вот до $n=627$ таковых точно нет (до $n=602$ я показывал их все выше), ну так приведите с большим значением $n$.
И если что, то это не моя гипотеза, а waxtep-а.

Я, кстати, склонен скорее верить, что для достаточно больших $n$ наступит $m_1>4$ Ведь $m_2$ и все прочие меняются, так почему не $m_1$?

[waxtep]

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

Можно написать общую формулу для нечетного $R_n$, приходящего к единице за $n$ утроений:

$$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)$$

Правда, $m_1$ выделен среди прочих тем, что присутствует только в первом (единственном положительном) слагаемом в правой части. Ну, это гадание на кофейной гуще, в общем

[MGM]

Все понятно. Я пас. Это уже клуб ньюферматиков..
Но чтобы вам было нескучно, предпоследнее число перед 1 может быть толко вида:
1×4+1 =5
5×4+1=21
21×4÷1=85
85×4+1=341
И так далее. Все эти числа требуют одного умножения на три, с последующим делением на степень двойки.

[Dmitriy40]

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

Но чтобы вам было нескучно, предпоследнее число перед 1 может быть толко вида:

Эта банальность следует прямо из условия $2^n\equiv1\pmod3$.
Я надеялся у Вас есть что-то не банальное ...

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

Я, кстати, склонен скорее верить, что для достаточно больших $n$ наступит $m_1>4$ Ведь $m_2$ и все прочие меняются, так почему не $m_1$?

Ну я об этом говорил ещё во втором же сообщении темы.

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

У меня это видимо два в степени вектор (как поэлементная операция), PARI сразу встает на дыбы и переводит в тип с плавающей точкой; я там поэтому результат в round() обернул. А << для вектора не сделаешь, ошибка несоответствия типов. Я-то привык к Matlab-у, где возня с матрицами всегда существенно быстрее ручного цикла, а тут видимо необязательно так.

Я думаю тормоза скорее в принципе из-за работы со сложными объектами типа векторов и матриц, это же требует выделения/освобождения памяти под временные переменные (а PARI тормозит даже на простых одиночных переменных, посмотрите выше про 48с vs 73с). Плюс наверняка тормозит (по сравнению с нормальными языками) вызов процедур. Плюс огромное количество итераций (у меня, у Вас оно превращается в огромные списки), которые тоже не быстрые даже сами по себе. Я потому и думаю что Ваш метод будет тормознее моего в любом случае - оперировать сложными объектами (списками чего угодно) всегда сложнее простого рекурсивного вызова. А если уж у Вас объём объектов превысит размер кэшей процессора (L3) или даже памяти вообще ... настанет вообще мрак со скоростью. Хотя количество итераций наверное может быть на порядки меньше моего (отсутствует рекурсивный проход глубже для каждого варианта вектора на каждом шаге), впрочем и у меня рекурсия чаще обрывается достаточно быстро. Так что вопрос кто когда быстрее - непростой.
Может быть таки соберусь и перепишу свой код (он как бы несложный) на дельфи или сразу асме, посмотрим насколько выйдет быстрее.

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

два в степени вектор (как поэлементная операция), PARI сразу встает на дыбы и переводит в тип с плавающей точкой;

Можно делать так, заодно не будете ограничены точностью плавающих чисел:

? apply(x->2^x,[1,2,3])
%1 = [2, 4, 8]
? apply(x->1<<x,[1,2,3])
%2 = [2, 4, 8]

apply это общее средство поэлементных операций над объектами. Как и select для произвольных выборок по некоему условию.

[waxtep]

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

apply это общее средство поэлементных операций над объектами.

Да можно было вообще написать что-то типа vectorv(px,k,(R*2<<(2*k)-1)/3), это я что-то тупанул, писал быстро и не приходя в сознание А внутри этих команд создания векторов и матриц и сидит apply скорее всего. А то как-то слишком уж тормозит, там для маленьких $n$ тысячи-десятки тысяч вариантов на каждом шаге, это не так много, учитывая элементарность проводимых операций; concat() кстати тоже один из подозреваемых, я как-то натыкался, что эта штука можем работать безумно медленно, видимо из-за неоптимальных манипуляций с памятью. В общем, мелкой оптимизацией я еще позанимаюсь, чтобы выйти на уже настоящие ограничения метода

[Dmitriy40]

Написал, на асме, затестил скорость: $R_{40}=41$ за 0.06с, $R_{50}=731$ за 0.3с, $R_{54}=1145$ за 0.6с, $R_{60}=1583$ за 1.7с, $R_{65}=871$ за 5.2с, $R_{70}=3567$ за 34с, $R_{75}=3695$ за 1.6м, $R_{80}=7785$ за 6.1м (и большую часть уже после нахождения ответа), $R_{81}=10087$ за 8.2м, $R_{85}=8351$ за 25м. Видно что всё равно непрактично, хоть и на пару порядков быстрее PARI.
К тому же я немного сжульничал: ограничил все промежуточные $r_i <2^{64}/3$, но это не приводит к ошибкам до $n<531$ (правда априори это неизвестно). Т.е. нормальная прога будет ещё несколько медленнее.

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

concat() кстати тоже один из подозреваемых,

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

[waxtep]

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

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

Вот это дало два порядка (минуты вместо часов для $n$ в районе $30\ldots40$ , уже приятно):

if(px>=1,ma=vectorv(px,k,2*k);un=vectorv(px,v,1);sa=vectorv(px,k,ma[k]+s);
Ra=vectorv(px,k,(R<<(2*k)-1)/3);
Rnext=matconcat([Rnext;matconcat([Ra,sa,un*m,ma])]));

Больше нет плавающего типа
Чтобы избавиться от конкатов, нужно колдунство с индексами устраивать, что-то типа разворачивания матрицы в вектор, и/или более аккуратно продумать подходящие структуры данных. Тогда останется только один внешний цикл, все остальное будет спрятано в работу с матрицами встроенными методами. Так, в принципе, можно надеяться подобраться к границе практического применения, попробую

[Dmitriy40]

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

[MGM]

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

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

Зря вы пользуетесь десятичным логарифмом.
Двоичный, lb, для этой задачи подходит лучше.
Ну и кроме того, вы уверены, что могли просчитать все нечетные числа до $2^{42} $? Я то в курсе, что максимум для таких чисел где-то в районе 64 бит, но это требуется еще доказать. Значит обычные integer64 могут и не потянуть, а biginteger c произвольным битовым размером - это дни вычислений. Ну и 603 - что-то многова-то.

-- Ср ноя 22, 2023 16:39:43 --

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

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

Но чтобы вам было нескучно, предпоследнее число перед 1 может быть толко вида:

Эта банальность следует прямо из условия $2^n\equiv1\pmod3$.
Я надеялся у Вас есть что-то не банальное ...

У вас супер небанальное. :)
Так как ваша формула неверна. Видимо, забыли двойку в степени пририсовать.
Про 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}$
Если непонятно, спросите профессиональных математиков. Если такие есть в вашем окружении.

[MGM]

Конечно, $m_1=4$. for min. Sorry.

[Dmitriy40]

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

Ну и кроме того, вы уверены, что могли просчитать все нечетные числа до $2^{42} $?

Да, я уверен. До 200e12 уже. Потому что на асме и плюс две техники ускорения счёта (кроме многопоточности).

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

Я то в курсе, что максимум для таких чисел где-то в районе 64 бит, но это требуется еще доказать. Значит обычные integer64 могут и не потянуть, а biginteger c произвольным битовым размером - это дни вычислений. Ну и 603 - что-то многова-то.

Не знаю про какой максимум Вы говорите, но все числа до $2^{64}$ при операциях $3x+1$ никогда не уходят выше $2^{128}$ (этот факт есть в OEIS), а обработку 128-битных чисел я реализовал (вместе с контролем переполнения). BigInteger без надобности, этими тормозами пользуйтесь сами, на Питоне, R и прочих языках.
И да, дни вычислений. Но я написал многопоточный код и уже 5 дней считаю им, о чём выше в теме сказал.
И да, уже досчитаны все $n<627$ (до 133e12) и ещё шесть штук до $n=687$.