Количество представлений чётных чисел суммой двух простых

[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.

[Dmitriy40]

Замена (t+1)\2 на ceil(t/2) ещё немножко ускоряет, на 7%.

[wrest]

Dmitriy40
Тогда уж целиком
my(q=Vecrev(Pol(v)^2)[1..N\2]));q=ceil(q/2);q[2]=1;

[Dmitriy40]

wrest
Зачем лишнее присваивание?
q=ceil(Vecrev(Polrev(v)^2,N\2)/2); q[2]=1;
Ещё чуть быстрее.

[wrest]

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

Зачем лишнее присваивание?

У меня почему-то в векторе оказывались дроби, видать скобки не так сосчитал. Сейчас норм.
Я пишу в андроиде, в приложении QuickEdit а оно почему-то скобки не подсвечивает или я недонастроил... Мучаюсь этим

По скорости одинаково (типа 3,840 против 3,900), но по краткости лучше конечно без лишней операции.

[wrest]

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

Теперь у нас есть полином $f(x)$. Давайте посчитаем $\widehat f$ - его дискретное преобразование Фурье, $\widehat f_k = f(\omega^k)$, где $\omega = \sqrt[N]{1}$. Понятно, что $\widehat{f \cdot f}_k = (\widehat f)_k^2$. Поэтому теперь наша задача сводится к вычислению дискретного преобразования Фурье.

Реализация через встроенные функции pari/gp: rootsof1(n), fft(w,P) и fftinv(w,P) -- возвращает целые числа если входные векторы из целых (не надо округлять) но работает на порядок медленнее умножения полиномов (применительно к нашему случаю).

[mihaild]

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

Я бы эти количества назвал функцией Гольдбаха

Уже есть термин разбиение Гольдбаха (ровно представление числа $2n$ в виде суммы двух простых), так что можно назвать "число разбиений Гольдбаха". Чуть длиннее, зато без новго термина.

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

Реализация через встроенные функции pari/gp: rootsof1(n), fft(w,P) и fftinv(w,P)

А что именно оно считает? Преобразование Фурье над конечным полем?

[wrest]

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

А что именно оно считает?

Дополняет массивы входных векторов нулями до ближайшей к сумме их длин степени двойки
Вычисляет ДПФ по корням из единцы для обоих массивов.
Поэлементно умножает массивы
Делает обратное ДПФ, отбрасывает мнимые части, округляет (все-таки) и нормализует результат.

Это делается в аналоге scipy.signal.fftconvolve