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

[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