Гипотеза о симметричных простых близнецах

[mihaild]

wrest в сообщении #1708665 писал(а):

Вычислительнкя сложность примерно $O(\pi^2(n))$

Не знаю, как это реализовано в pari/gp, но вообще произведение многочленов можно посчитать за $O(NlogN)$ (тут есть некоторые хитрости с тем, что нам нужна достаточно точная вещественная арифметика, но в данном случае, когда коэффициенты сравнительно небольшие, просто float32 достаточно).

[wrest]

mihaild в сообщении #1708662 писал(а):

А что дальше с этим предлагается делать?

Ну... это было чисто вычислительное упражнение на тему "оптимизации". Свертка оказалась весьма поучительным примером. В pari/gp нет встроенной функции свертки двух рядов чисел почему-то, но есть очень быстрая (я бы даже сказал неожиданно быстрая) арифметика полиномов.

Практической целью было посмотреть какой длины бывают последовательности соседних чётных чисел такие, что вычисляемое количество пар простых уменьшается, и найти первые такие числа в уменьшающихся последовательностях.
Оказалось что первая цепочка из 4 чисел начинается с числа 620620, и дальше до 10^8 более длинных нет.
Вот она:
n=620620 pairs=5482
n=620622 pairs=5408
n=620624 pairs=2733
n=620626 pairs=2726
и дальше увеличивается:
n=620628 pairs=5420

На массиве 10^8 закончилась память (я могу отдать 8ГБайт памяти под стек pari/gp на планшете, и если отдать больше то планшету плохеет).

Ну и вообще, ТС же тут дикие заявления делал о монотонности, надо было глянуть как оно нк самом деле.

-- 09.11.2025, 01:33 --

mihaild в сообщении #1708666 писал(а):

Не знаю, как это реализовано в pari/gp, но вообще произведение многочленов можно посчитать за $O(NlogN)$ (тут есть некоторые хитрости с тем, что нам нужна достаточно точная вещественная арифметика, но в данном случае, когда коэффициенты сравнительно небольшие, просто float32 достаточно).

Я тоже в код не смотрел, делается ли там именно ДПФ. И там же в этом $O(NlogN)$ по сути $N=\pi(n)$ поскольку мы считаем только простые.

P.S. Я бы эти количества назвал функцией Гольдбаха. Не знаю какая от неё польза, но его имени функции нет, пусть бы была эта.

-- 09.11.2025, 02:03 --

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

И после исправления он такой же по скорости как и не улучшенный.

Но идея с vecsmall верная, и разрабы рекомендуют.

[Dmitriy40]

wrest в сообщении #1708667 писал(а):

И там же в этом $O(NlogN)$ по сути $N=\pi(n)$ поскольку мы считаем только простые.

По моему нет, считается весь полином, а что там много нулевых коэффициентов в ДПФ вроде бы не используется.
Вообще круто, да.

[mihaild]

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

По моему нет, считается весь полином, а что там много нулевых коэффициентов в ДПФ вроде бы не используется.

Более того, сами коэффициенты преобразования Фурье всё равно вряд ли часто нулевые, так что при обратном считать придётся всё.

[Dmitriy40]

wrest
Улучшил код, работает почти вдвое быстрее (потому что обрабатываются только нечётные степени):
v=vectorsmall(precprime(N-3)\2+1); forprime(p=3,#v*2-1, v[#v-p\2]=1); ff=Pol(v)^2;
q=vectorsmall(N\2,n, (polcoef(ff,n-1)+1)\2); q[2]=1;\\включая самопары, плюс коррекция N=4
Индекс n в q[n] отвечает за число 2*n.

[wrest]

Dmitriy40
Прекрасно! Для N=10^8 у меня считает 3,2 секунды в режиме интерпретации.
t_VECSMALL конечно ускоряет всё. Индекс и компоненты становятся long, и нет тяжелой машинерии арифметики произвольной точности. Думаю там ещё сколько-то можно срезать исключив polcoef, но уже не много.

[vicvolf]

mihaild в сообщении #1708662 писал(а):

это как раз число упорядоченных способов представить $n$ в виде суммы двух простых.

Асимптотика количества таких чисел давно известна $C\int_2^x \frac{dt}{\ln^2(t)}$, где $C=0,66...$.

[wrest]

wrest в сообщении #1708691 писал(а):

Думаю там ещё сколько-то можно срезать исключив polcoef, но уже не много.

Вот как-то так, без polcoef и без сохранения промежуточного результата возведения полинома в квадрат
v=vectorsmall(precprime(N-3)\2+1); forprime(p=3,#v*2-1, v[#v-p\2]=1);
q=apply(x->(x+1)\2,vecextract(Vecrev(Pol(v)^2),[1..N\2]));q[2]=1;
Теряется правда преимущество t_VECSMALL для вектора результата, но тем не менее это немного быстрее, у меня 2,8сек против 3,2сек для N=10^7

[Dmitriy40]

wrest
Чтобы не заморачиваться с обратной записью коэффициентов есть Polrev() вместо Pol():
v=vectorsmall(precprime(N-3)\2+1); forprime(p=3,#v*2-1, v[p\2+1]=1); ff=Polrev(v)^2;

А коэффициенты можно вернуть из t_POL вызовом Vec()/Vecsmall(), только они выдаются в обратном порядке (начиная со старших) и приходится переставлять при вычислении:
w=Vecsmall(ff); q=vectorsmall(N\2,i, (w[#w-i+1]+1)\2); q[2]=1;
И это замедляет на 5%.

-- 09.11.2025, 14:24 --

wrest
Ваш вариант требует заметно больше памяти на промежуточные результаты.

Вместо vecextract() можно написать просто
q=apply(t->(t+1)\2, Vecrev((Polrev(v)^2))[1..N\2]); q[2]=1;

[wrest]

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

Вместо vecextract() можно написать просто

Точно! Крутилось в голове же это.

[Dmitriy40]

wrest
Можно вот так сделать:
q=vecextract(Vecsmall(Polrev(v)^2), Vecrev(Vecsmall([#v*2-N\2..#v*2-1]))); for(n=1,#q, q[n]=(q[n]+1)\2); q[2]=1;
Тут зеркалится не вектор, а список его перестановки, который короче и его проще перевернуть, соответственно сам вектор можно оставить vectorsmall. Правда apply() не умеет с vectorsmall, потому просто for.
Работает даже чуть быстрее.

[wrest]

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

Чтобы не заморачиваться с обратной записью коэффициентов есть Polrev() вместо Pol():

У меня с наскока не вышло, там надо следить что куда попадает...
Вообще эта заморочка с обратным порядком коэффициентов в pari/gp выпила много крови у меня и LLM-ов

[Dmitriy40]

wrest
Оказывается у Vec, Col, Vecrev, ColRev, Vecsmall есть второй параметр. С ним становится совсем просто:
q=(Vecrev(Polrev(v)^2,N\2)+vector(N\2,i,1))\2; q[2]=1;
Требует тоже больше памяти, зато работает чуточку быстрее.
Но vectorsmall тут не применить так как их нельзя складывать, вот же засада!

-- 09.11.2025, 16:47 --

Пока самые быстрые такие варианты:
q=apply(t->(t+1)\2, Vecrev(Polrev(v)^2, N\2])); q[2]=1;
q=(Vecrev(Polrev(v)^2, N\2)+vector(N\2,n,1))\2; q[2]=1;
Последний быстрее где-то на 2%. Но памяти надо больше.
C vecsmall все медленнее, процентов на 5-10.

[wrest]

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

q=apply(t->(t+1)\2, Vecrev(Polrev(v)^2, N\2])); q[2]=1;

Вы это проверяли, двойное зеркалирование в Vecrev(Polrev(v)^2)? Возвращается в итоге что надо?

-- 09.11.2025, 17:18 --

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

Оказывается у Vec, Col, Vecrev, ColRev, Vecsmall есть второй параметр.

Действительно, ну разрабы прям знали, что обрезание может быть быть частой операцией.

[Dmitriy40]

wrest в сообщении #1708731 писал(а):

Вы это проверяли, двойное зеркалирование в Vecrev(Polrev(v)^2)? Возвращается в итоге что надо?

Да, весь код рабочий, копирую только после сверки результата с образцом.

Кстати можно и без зеркаливания сделать (заполнение v[] то же):
q=apply(t->(t+1)\2, Vec(Pol(v)^2, N\2-2]));
Только пропадут первые два значения, 2 и 4, q[1] будет про 6, не про 2. Неудобно, зато короче.
Тут в полиноме перепутаны старшие и младшие степени, но так как нам нужна лишь симметричная сумма, то и плевать. За исключением что старшая степень (которая теперь про число 1) оказывается нулевой и из вектора пропадает, потому он и обрезается на 2 меньше. Кривовато, но забавно.

-- 09.11.2025, 18:19 --

Кстати, ограничение N\2 немного зажато, правильные значения вплоть до nextprime(N)+2.