Алгоритм Гольдбаха

[RAiNERR]

Какой на данный момент времени существует алгоритм , который находит в бинарной проблеме Гольдбаха все простые наборы представления четного числа?
Хотелось бы сравнить его со своим алгоритмом.

[Sonic86]

Вряд ли есть какой-то особый специальный алгоритм.
Простейший способ, для заданного $n$ вычислить $\pi(n/2)-1$ нечетных простых (решетом) и для каждого $p\leqslant \frac{n}{2}$ проверить двоичным поиском, лежит ли $n-p$ в массиве простых. Работает за $O(n\ln n)$ итераций (если принять во внимание разрядность).

Можно, конечно, приведенный способ "склеить": выписать $\frac{n}{2}$ разложений числа в сумму двух нечетных и проводить решето уже над ними.

[RAiNERR]

Спасибо.

[Батороев]

Можно из натурального ряда до $\frac {n}{2}$ исключить решетом числа, кратные простым $p<\sqrt {n}$, а также числа, имеющие остаток $n\pmod p$. При этом в "сухом остатке" останутся простые $q$. Вторые простые слагаемые, соответственно, $(n-q)$. При этом не забыть проверить пары с самими $p$.

-- 17 апр 2013 02:06 --

Второй вариант: Из ряда квадратов до $ \left(\frac{n}{2}\right)^2$ исключить числа, имеющие остаток $\left(\frac {n}{2}\right)^2\pmod p$. В "сухом остатке" останутся числа $a^2$ такие, что простые слагаемые будут $(\frac{n}{2}\pm a)$. Также не забыть проверить пары с $p$.

[Cash]

Sonic86 в сообщении #711211 писал(а):

Простейший способ, для заданного $n$ вычислить $\pi(n/2)-1$ нечетных простых (решетом) и для каждого $p\leqslant \frac{n}{2}$ проверить двоичным поиском, лежит ли $n-p$ в массиве простых. Работает за $O(n\ln n)$ итераций (если принять во внимание разрядность).

Можно придумать еще пару трюков, например - разделить массивы простых на два - $ \pm 1 \pmod 6$ и проверять в соответствующем массиве, а также вместо бинарного поиска - прицелиться один раз, а далее двигаться сверху вниз и максимум пару сравнений делать, но идейно вряд ли сейчас есть что-то лучше (учитывая относительно небольшое количество проверенных на данный момент - что-то порядка $10^{18}$).

У меня следующий вопрос возник:
Назовем простое число $p$ гольдбаховым, если существует такое число $N$, что для любого гольдбахового разложения на сумму двух простых $N = q_1+q_2$ выполнено $q_1 \geqslant p$.

1. Ведется ли какая-то статистика по таким числам? Есть ли у них общепринятое название? Какое сейчас наибольшее известное?
2. Конечно ли множество гольдбаховых чисел?
3. Существуют ли простые числа, не являющиеся гольдбаховыми?

[Xaositect]

Cash в сообщении #711436 писал(а):

2. Конечно ли множество гольдбаховых чисел?

Так как между простыми числами есть сколь угодно большие промежутки, существуют и сколь угодно быльшие гольдбаховы числа.

[Cash]

Точно. Ответ на поверхности.
Остается тогда вопрос №3, хотя вряд ли это уж настолько интересная задача, как мне казалось в начале...

[megamix62]

Метод решета Бруна стр.95 у Троста

-- 25.04.2013, 21:48 --

Cash в сообщении #711436 писал(а):

Sonic86 в сообщении #711211 писал(а):

Простейший способ, для заданного $n$ вычислить $\pi(n/2)-1$ нечетных простых (решетом) и для каждого $p\leqslant \frac{n}{2}$ проверить двоичным поиском, лежит ли $n-p$ в массиве простых. Работает за $O(n\ln n)$ итераций (если принять во внимание разрядность).

Можно придумать еще пару трюков, например - разделить массивы простых на два - $ \pm 1 \pmod 6$ и проверять в соответствующем массиве, а также вместо бинарного поиска - прицелиться один раз, а далее двигаться сверху вниз и максимум пару сравнений делать, но идейно вряд ли сейчас есть что-то лучше (учитывая относительно небольшое количество проверенных на данный момент - что-то порядка $10^{18}$).

У меня следующий вопрос возник:
Назовем простое число $p$ гольдбаховым, если существует такое число $N$, что для любого гольдбахового разложения на сумму двух простых $N = q_1+q_2$ выполнено $q_1 \geqslant p$.

1. Ведется ли какая-то статистика по таким числам? Есть ли у них общепринятое название? Какое сейчас наибольшее известное?
2. Конечно ли множество гольдбаховых чисел?
3. Существуют ли простые числа, не являющиеся гольдбаховыми?

Можно ли на примере что такое за простое число ( $p$ гольдбаховое)