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

[mihaild]

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

1. Неизвестно - каждое или не каждое. Проверено до $4\cdot 10^{18}$. Строгого доказательства что "каждое" -- нет.

Порождает-то точно каждое. Никто же не говорил, что множество непустое.

Ryzl в сообщении #1708632 писал(а):

то я бы не стал здесь, на форуме математиков, писать про это. Зачем мне это было бы нужно

Хороший вопрос. Зачем Вам нужно здесь про что-то писать?

Ryzl в сообщении #1708639 писал(а):

Что не так в этом утверждении?

Строго говоря, нужно сказать, что значит "порождает".
Но ладно, это легко исправляется: для любого четного числа $n$ существует множество $A_n$, состоящее из пар простых чисел, дающих в сумме $n$. Это утверждение несложно доказывается с помощью аксиомы выделения.
В таких терминах гипотеза Гольдбаха формулируется так: верно ли, что для любого четного $n > 2$, $A_n$ непусто?

[Ryzl]

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

Ryzl в сообщении #1708639 писал(а):

Я выразился строго.
1. Каждое четное число порождает множество пар чисел дающих в сумме это четное число.

Что не так в этом утверждении?

Неизвестно верно оно или неверно. Каждое или всё же не каждое. Гипотеза Гольдбаха пока не доказана и не опровергнута.

Ryzl в сообщении #1708639 писал(а):

Что не так в этом утверждении?

Вот ещё что не так: 2 не порождает (потому что 1 не простое). Уже поэтому это утверждение точно неверно.

При чем здесь гипотеза Гольдбаха????
1. Каждое четное число порождает множество пар чисел дающих в сумме это четное число.

[Dmitriy40]

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

Но ладно, это легко исправляется: для любого четного числа $n$ существует множество $A_n$, состоящее из пар простых чисел, дающих в сумме $n$. Это утверждение несложно доказывается с помощью аксиомы выделения.

А Вы уверены что ТС помнит что множества бывают и пустыми? А то примет это за доказательство гипотезы Гольдбаха ...

Ryzl в сообщении #1708643 писал(а):

При чем здесь гипотеза Гольдбаха????
1. Каждое четное число порождает множество пар чисел дающих в сумме это четное число.

Я извиняюсь! Упустил что нет слова "простых". Тогда да, очевидно верно. Сколь и тривиально.
В таком случае пункт 2 тоже верный. И тоже банальный.
А пункт 3 - непонятно, смысл "глобальное увеличение". Можно ли его доказать пока тоже непонятно.

[Ryzl]

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

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

Но ладно, это легко исправляется: для любого четного числа $n$ существует множество $A_n$, состоящее из пар простых чисел, дающих в сумме $n$. Это утверждение несложно доказывается с помощью аксиомы выделения.

А Вы уверены что ТС помнит что множества бывают и пустыми? А то примет это за доказательство гипотезы Гольдбаха ...

Ryzl в сообщении #1708643 писал(а):

При чем здесь гипотеза Гольдбаха????
1. Каждое четное число порождает множество пар чисел дающих в сумме это четное число.

Я извиняюсь! Упустил что нет слова "простых". Тогда да, очевидно верно. Сколь и тривиально.
В таком случае пункт 2 тоже верный. И тоже банальный.
А пункт 3 - непонятно, смысл "глобальное увеличение". Можно ли его доказать пока тоже непонятно.

Хорошо, с первым пунктом разобрались
1. Каждое четное число порождает множество пар чисел дающих в сумме это четное число. (это тривиально, как Вы говорите, но здесь нужно все проговаривать, тем более что некоторые невнимательно читают)


Переходим ко второму пункту.

2. Это непустое множество состоит из четырех подмножеств (C-C, С-П, П-С, П-П)

Это тоже тривиально? И верно?

[пианист]

Ryzl в сообщении #1708645 писал(а):

2. Это непустое множество состоит из четырех подмножеств (C-C, С-П, П-С, П-П)

Это тоже тривиально? И верно?

Есть небольшая заморочка, как пару из составного и простого отнести ко 2 или 3 подмножеству в Вашей классификации, но как-то можно договориться. А так, да, все верно.

[Dmitriy40]

Ryzl в сообщении #1708645 писал(а):

2. Это непустое множество состоит из четырех подмножеств (C-C, С-П, П-С, П-П)

Это тоже тривиально?

Да.

Ryzl в сообщении #1708645 писал(а):

И верно?

Нет: для числа 2 подмножества П-П и П-С и С-П и С-С все пустые (потому что число 1 не является ни простым, ни составным), соответственно непустое множество пар $\{(1,1)\}$ состоит не только из этих четырёх подмножеств.
И для числа 6 множество пар $\{(1,5),(2,4),(3,3),(4,2),(5,1)\}$ содержит пары $(1,5),(5,1)$, которые не попадают ни в одно из подмножеств С-С, П-П, С-П, П-С.
И такие две пары, не попадающие в указанные 4 подмножества, будут для любого чётного числа больше 2 (для него такая пара одна).

И для совсем уж корректности надо упоминать что речь про натуральные числа (и без 0). Потому что 0 считается чётным числом. И тоже ни простым, ни составным. Но натуральным или целым - вопрос определений. В России обычно целым (не натуральным).

[Ryzl]

Хорошо, договорились о втором пункте.

Второй пункт действителен для четных чисел больше 16. (по аналогии с гипотезой Гольдбаха, в которой тоже есть нижняя граница)

Относительно пар, я специально выделил в отдельные подмножества С-П и П-С (т.е. составное-простое и простое-составное)

Т.е. второй пункт тоже верен?

[Dmitriy40]

Ryzl в сообщении #1708649 писал(а):

Т.е. второй пункт тоже верен?

Нет не верен.
В какое подмножество относите пару $(199,1)$ для чётного числа $200$?

-- 08.11.2025, 21:53 --

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

Вы быстрее считать научились?

А вот теперь научился.
Смотрите, код
q=vector(10^5); forstep(x=4,#q,2, n=0; forprime(p=3,x/2, isprime(x-p)&&n++); q[x]=n)
работает 22с.
А если в q[] накапливать количество вариантов, то код получается таким
q=vector(10^5); forprime(a=3,#q/2, forprime(b=a,#q-a, q[a+b]++))
и работает уже 14с.
А теперь финт ушами: меняем vector на vectorsmall и получаем ускорение первого варианта до 17с, а второго до 2.5с!
А поменяв порядок циклов:
q=vector(10^5); forprime(a=#q/2,#q-3, forprime(b=3,#q-a, q[a+b]++))
можно ускорить до 1.3с.
До 1е6 первый вариант считает 22м13с, второй 2м46с, а улучшенный 1м20с (все с vectorsmall).

Вероятно и это не предел.

[Ryzl]

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

Ryzl в сообщении #1708649 писал(а):

Т.е. второй пункт тоже верен?

Нет не верен.
В какое подмножество относите пару $(199,1)$ для чётного числа $200$?

Это смотря как вы рассматриваете число 1. Составное или простое?

Из простых его исключили чтобы разложение на простые множители было однозначным, так? И определение простых подкрутили с определением "...числа большие 1..."

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

[Dmitriy40]

Ryzl в сообщении #1708652 писал(а):

Это смотря как вы рассматриваете число 1. Составное или простое?

Ни такое, ни такое.

Ryzl в сообщении #1708652 писал(а):

Из простых его исключили чтобы разложение на простые множители было однозначным, так?

Так.
Только составным оно не стало. Потому что по определению составное делится на какие-то простые, а 1 не делится.

И если Вы рассматриваете числа как-то по другому, то это надо прямо проговаривать. А лучше так вообще не делать.

-- 08.11.2025, 22:04 --

Ryzl в сообщении #1708652 писал(а):

И определение простых подкрутили с определением "...числа большие 1..."

Можно и так, но обычно подкручивают по другому: простое число это такое, которое имеет ровно два (подразумевается разных!) делителя - 1 и само себя.

[Someone]

Ryzl в сообщении #1708652 писал(а):

Из простых его исключили чтобы разложение на простые множители было однозначным, так?

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

[wrest]

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

Вероятно и это не предел.

Это точно не предел. ИИ тут мне полоскает мозг что если свернуть два массива то получишь что надо. Потом это сводится к возведению в квадрат полинома вида $x^2+x^3+x^5+...$ с простыми степенями, ну и всё это мгновенно. Но ходит по кругу то непопадая в индексы, то придумывая новый синтаксис для pari и я бросил затею, но там явно есть путь очень, очень быстрый.

[mihaild]

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

Потом это сводится к возведению в квадрат полинома вида $x^2+x^3+x^5+...$ с простыми степенями, ну и всё это мгновенно

Это не мгновенно, но это за $O(N\logN)$ делается.
Алгоритм из слегка продвинутых, но широко известный. Если мы возведем в квадрат Ваш полином, то коэффициент при $x^n$ - это как раз число упорядоченных способов представить $n$ в виде суммы двух простых.
Теперь у нас есть полином $f(x)$. Давайте посчитаем $\widehat f$ - его дискретное преобразование Фурье, $\widehat f_k = f(\omega^k)$, где $\omega = \sqrt[N]{1}$. Понятно, что $\widehat{f \cdot f}_k = (\widehat f)_k^2$. Поэтому теперь наша задача сводится к вычислению дискретного преобразования Фурье. И это легко, если заметить, что для если $f = g^2$, то $f(\omega) = g(\omega^2)$, а если $f = x \cdot g^2$, то $f(\omega) = \omega \cdot g(\omega^2)$ - тем самым вычисление ДПФ для $f$ сводится к его вычислению для двух полиномов вдвое меньшей степени.
На практике это выражается в том, что scipy справляется со свёрткой 50 миллионов элементов (для ускорения процесса я взял только нечетные простые) за 19с (для калибровки - sympy на той же машине требует 2 минуты на собственно вычисление первых 100 миллионов простых).
А что дальше с этим предлагается делать?

[Dmitriy40]

Упс, мой улучшенный код (с переставленными циклами) работает неправильно.
И после исправления он такой же по скорости как и не улучшенный.

[wrest]

Dmitriy40
В общем, бинго!
Массив 10 млн считается за 9 сек в интерпретаторе (без компиляции).

1. ? g_vec(N) = { 
2.   if (N < 4, return(vector(N, k, 0))); 
3.   my(v = vector(N+1)); 
4.   forprime(p = 2, N, v[N - p + 1] = 1); 
5.   my(ff = Pol(v)^2); 
6.   vector(N, n, 
7.     if(n % 2, 0, 
8.        my(c = polcoef(ff, n)); 
9.        (c + 1) \ 2;  \\ включая самопары 
10.     ) 
11.   ); 
12. } 
13. ? gv=g_vec(10^7); 
14.   *** sqr: Warning: increasing stack size to 800000000. 
15.   *** sqr: Warning: increasing stack size to 1600000000. 
16. time = 9,714 ms. 
17. ? gv[1234568] 
18. %176 = 4843 
19. ? 

Идея проста до неприличия "и как я сразу не догадался"
Если у нас есть полином у которого единичные коэффициенты только при простых степенях, то возводя его в квадрат, получаем полином у которого в качестве коэффициентов как раз нужные нам суммы. То есть при степени 8 будет коэффициент 2 т.к. её можно получить только двумя способами: $x^3x^5+x^5x^3=2x^8$ -- делим его на два и всё. Осталось разобраться с т.н. "самопарами" когда пару составляют два одинаковых простых. Ну это тоже просто.

Спасибо Qwen-у который все-таки доделал за ChatGPT тонкости с индексированием а последнему за идею.
Вычислительнкя сложность примерно $O(\pi^2(n))$ но дикая оптимизация полиномиальной арифметики в pari делает своё дело.

-- 09.11.2025, 01:17 --

mihaild
О, пока писал свой пост, вы меня опередили с объяснением.