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

[Ryzl]

Вот найден первый претендент

Текущее число 2N = 2^{50474}

2^{50474} - 3 --- Prime Number

3 часа работы.

Осталось как то доказать что это простое?

В принципе способ рабочий. Нахождение претендентов.

[Dmitriy40]

Уже всего лишь 2 в степени, меньше 15200 цифр.

[Ryzl]

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

Уже всего лишь 2 в степени, меньше 15200 цифр.

До рекорда конечно как до луны пешком. Согласен :)

Это просто обкатка метода. Т.е. не только числа Мерсенна могут быть кандидатами. А числа вида P=2^{k}-p
Где:
P - кандидат
k - натуральное число
p - простое число

[Dmitriy40]

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

Т.е. не только числа Мерсенна могут быть кандидатами.

Разумеется кандидатами могут быть любые числа, лучше нечётные или даже вида $6k\pm1$ или ещё более замороченные.
Вот только числа Мерсенна выделены тем что для них есть практичный метод доказательства простоты Люка-Лемера, а для почти любых других такого метода нет. И потому числа Мерсенна можно проверить (и доказать!) на простоту гораздо большие чем почти любые другие.

[Ryzl]

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

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

Т.е. не только числа Мерсенна могут быть кандидатами.

Разумеется кандидатами могут быть любые числа, лучше нечётные или даже вида $6k\pm1$ или ещё более замороченные.
Вот только числа Мерсенна выделены тем что для них есть практичный метод доказательства простоты Люка-Лемера, а для почти любых других такого метода нет. И потому числа Мерсенна можно проверить (и доказать!) на простоту гораздо большие чем почти любые другие.

Ну вот, засада :)

Спасибо! Понятно, что мои числа никак за обозримое время не проверить на простоту.
Всем спасибо!

[wrest]

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

3 часа работы.

3 часа работы на что? Псевдопростота числа $2^{50474}-3$ устанавливается за 40 секунд на андроид планшете.

-- 15.10.2025, 09:38 --

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

Понятно, что мои числа никак за обозримое время не проверить на простоту.

Ессно, но есть ещё проблема. Надо показать, что ваши "кандидаты" чем-то лучше случайных нечётных чисел.

[Dmitriy40]

Да ничем они не лучше:

? s=vector(1000); n=0; x=10^500; while(n<100, forprime(p=3,#s, if(ispseudoprime(x-p), n++; s[p]++; break)); x+=2); x-10^500
%1 = 1364
time = 1min, 15,989 ms.
? s=vector(100); n=0; x=10^500; while(n<100, forprime(p=3,#s, if(ispseudoprime(x-p), n++; s[p]++; break)); x+=2); x-10^500
time = 49,688 ms.
%2 = 5684
? s=vector(10); n=0; x=10^500; while(n<100, forprime(p=3,#s, if(ispseudoprime(x-p), n++; s[p]++; break)); x+=2); x-10^500
time = 43,321 ms.
%3 = 38924
? s=vector(3); n=0; x=10^500; while(n<100, forprime(p=3,#s, if(ispseudoprime(x-p), n++; s[p]++; break)); x+=2); x-10^500
time = 43,056 ms.
%4 = 116088
? n=0; x=10^500; while(n<100, if(ispseudoprime(x-3), n++); x+=2); x-10^500
time = 43,019 ms.
%5 = 116088
? n=0; x=10^500; while(n<100, if(ispseudoprime(x+1), n++); x+=2); x-10^500
time = 43,103 ms.
%6 = 116084
? n=0; x=(10^500\6)*6; while(n<100, if(ispseudoprime(x-1), n++); if(ispseudoprime(x+1), n++); x+=6); x-10^500
time = 43,052 ms.
%7 = 116090
? n=0; x=(10^500\30)*30; while(n<100, foreach([1,7,11,13,17,19,23,29],d, if(ispseudoprime(x+d), n++)); x+=30); x-10^500
time = 43,023 ms.
%8 = 116090

Показано время нахождения 100 больших простых около $10^{500}$ и какой интервал проверен.
Одинаковое время для разных методов перебора говорит лишь о качестве реализации ispseudoprime(), что она тоже сама проверяет малые делители, а основное время тратится на проверку действительно простых, и потому последние пять вариантов фактически эквиваленты.

[Someone]

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

Вот найден первый претендент

Текущее число 2N = 2^{50474}

2^{50474} - 3 --- Prime Number

3 часа работы.

Осталось как то доказать что это простое?

Программа Primo должна справиться. Она использует метод эллиптических кривых и вырабатывает сертификат простого числа. Сколько времени потребуется для проверки вашего числа $2^{50474}-3$ — затрудняюсь сказать. Последняя версия для Windows была 3.0.9, у меня она обрабатывала знакочередующуюся сумму факториалов $2653!-2652!+2651!-2650!+...+1!$ (7934 цифры) аж $571$ час $50$ минут $16$ секунд. С увеличением числа затраты времени растут быстро. Работу программы можно прерывать и потом возобновлять.
Сейчас автор программы версию для Windows не поддерживает, есть версия 4.3.3 для Linux Ubuntu 18.04/x86-64 architecture (о других версиях Линукса Marcel Martin пишет, что не знает, работает ли там его программа). Программа может работать с числами до $50\,000$ цифр и может использовать до $64$ процессоров одновременно.
Вероятно, есть другие программы для проверки простоты, не вырабатывающие сертификат и потому работающие быстрее.

Есть программы, работающие с числами специальных видов. Например, программа PrimeForm GW. Последняя версия на данный момент — pfgw_win_4.1.3. Пример числа из указанного Вами диапазона $[10^{50000}/2,10^{50000}]$:

Primality testing (10^50000)/2+(10^16667)*28975-1 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 11
Running N+1 test using discriminant 17, base 1+sqrt(17)
Calling N+1 BLS with factored part 33.35% and helper 0.02% (100.08% proof)
(10^50000)/2+(10^16667)*28975-1 is prime! (165.1617s+0.0010s)

Сначала той же программой было выполнено просеивание чисел вида $10^{50000}/2+10^{16667}\times k-1$ из диапазона $1\leqslant k\leqslant 200\,000$ (прервал на $k=43172$, когда заметил, что один кандидат нашёлся). Сколько ушло времени, не заметил, кажется, дня три. Вот фрагмент лог-файла:

(10^50000)/2+(10^16667)*28974-1 has factors: 12917

(10^50000)/2+(10^16667)*28975-1 is 3-PRP! (23.0939s+9.0217s)
(10^50000)/2+(10^16667)*28976-1 has factors: 3^2

(10^50000)/2+(10^16667)*28977-1 has factors: 127

(10^50000)/2+(10^16667)*28978-1 has factors: 67

(10^50000)/2+(10^16667)*28979-1 has factors: 3

(10^50000)/2+(10^16667)*28980-1 has factors: 7

(10^50000)/2+(10^16667)*28981-1 has factors: 13

(10^50000)/2+(10^16667)*28982-1 has factors: 3

(10^50000)/2+(10^16667)*28983-1 has factors: 23

(10^50000)/2+(10^16667)*28984-1 has factors: 383

(10^50000)/2+(10^16667)*28985-1 has factors: 3^2

(10^50000)/2+(10^16667)*28986-1 has factors: 47

(10^50000)/2+(10^16667)*28987-1 has factors: 7

(10^50000)/2+(10^16667)*28988-1 has factors: 3

(10^50000)/2+(10^16667)*28989-1 is composite: RES64: [FC270A1E48E1DF7A] (23.8883s+9.2017s)
(10^50000)/2+(10^16667)*28990-1 has factors: 11

Прежде, чем браться за такое дело, полезно оценить ожидаемый объём работы.
Плотность простых чисел в районе большого числа $N$ равна примерно $\frac 1{\ln N}$, поэтому можно ожидать, что придётся проверить порядка $1:\frac 1{\ln N}=\ln N$ кандидатов.
У нас числа имеют величину порядка $10^{50000}/2$, и получаем $\sim\ln(10^{50000}/2)=50000\ln 10-\ln2\approx 115129$ кандидатов. Однако можно заметить, что числа рассматриваемого вида заведомо не делятся ни на $2$, ни на $5$, поэтому полученный результат нужно умножить на $\left(1-\frac 12\right)\left(1-\frac 15\right)=0{,}4$, и получится $\sim 46\,000$ кандидатов, так как из каждых $10$ чисел заранее отсеиваются $6$, и вероятность получить простое число увеличивается в $\frac{10}4=2{,}5$ раза. На самом деле может оказаться и меньше, и больше. Как повезёт.

Но Вы же хотите не просто большое простое число, а пару простых чисел, либо дающих заданную (чётную) сумму, либо симметричных относительно заданного числа. Впрочем, это одно и то же: два числа с заданной чётной суммой симметричны относительно половины этой суммы. Значит, Вам нужно, чтобы одновременно два числа оказались простыми. Вероятности для этих чисел надо перемножить.

Например, мы хотим получить сумму $10^{50000}$. Тогда мы можем искать пары простых чисел вида $\left\{10^{50000}/2+10^{16667}\times k-1,10^{50000}/2-10^{16667}\times k+1\right\}$. Для того, чтобы ни одно из этих чисел не делилось на $3$, нужно, чтобы $k$ при делении на $3$ давало остаток $1$, поэтому можно положить $k=3n-2$, где $n=1,2,3,\ldots$, и сократить объём работы в $3$ раза. (Такую работу можно проделать и для других простых делителей, но для $k$ получится несколько выражений.)
Поэтому ожидаемое количество пар проверяемых кандидатов будет порядка $\frac 13\times 46000^2\sim 700\,000\,000$.

Если не стремиться к примерно равным слагаемым, а наоборот, одно слагаемое выбирать среди небольших чисел, то можно подбирать, например, пары чисел вида $\left\{10^{16667}\times k-1,10^{50000}-10^{16667}\times k+1\right\}$. Тогда первое число будет простым с вероятностью примерно $\frac{2{,}5}{\ln\left(10^{16667}\times k\right)}=\frac{2{,}5}{16667\ln 10+\ln k}=\frac 1{6666{,}8\ln 10+(\ln k)/2{,}5}$ (откуда берётся множитель $2{,}5$, объяснялось выше), а второе — с вероятностью примерно $\frac{2{,}5}{\ln 10^{50000}}=\frac{2{,}5}{50000\ln 10}=\frac 1{20000\ln 10}$. Слагаемым $\ln k$ можно пренебречь по сравнению с $16667\ln 10$, так как ожидаемое значение $\ln k$ вряд ли превосходит $10\ln 10\approx 23$.
Как и в первом варианте, можно проверить, что число $k$ должно делиться на $3$, поэтому можно положить $k=3n$, где $n=1,2,3,\ldots$, и сократить объём работы в $3$ раза.
В итоге ожидаемое количество проверяемых пар кандидатов будет порядка $\frac 13(20000\ln 10)(6666{,}8\ln 10)\approx 240\,000\,000$.

Это меньше, чем в предыдущем примере, но всё равно много. Уменьшить показатель степени $16667$ нельзя. Используемые тесты предполагают следующие условия.
Пусть мы проверяем большое число $N$. Пусть $N-1=F_1R_1$ и $N+1=F_2R_2$, причём, числа $F_1$ и $F_2$ полностью разложены на простые множители, а простые множители чисел $R_1$ и $R_2$ неизвестны. Тогда должно выполняться хотя бы одно из неравенств $N<F_1^3$ или $N<F_2^3$ (на самом деле условия чуть-чуть слабее, но совсем ненамного).
Заметим, что для наибольшего из двух чисел в рассмотренных примерах гарантированно факторизуемая часть числа $N\pm 1$ равна $10^{16667}$ и неравенство $\left(10^{16667}\right)^3=10^{50001}>N$ выполняется, в то время как $\left(10^{16666}\right)^3=10^{49998}<N$. Может быть, удастся уменьшить показатель $16667$ до $16665$ или до $16664$, используя дополнительные возможности программы, но я не проверял, а экономия объёма работы будет незначительной.

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

Зарядил программу на рекорд
10^{50000}/2 до 10^{50000}

Что за рекорд? \glqq Красивое\grqq чётное число, которое является суммой двух простых? А какой текущий рекорд?

P.S. Очень много информации о простых числах и их поиске можно найти на сайте Prime Pages