2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: Гипотеза о симметричных простых близнецах
Сообщение14.10.2025, 12:18 
Вот найден первый претендент

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

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

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

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

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

 
 
 
 Re: Гипотеза о симметричных простых близнецах
Сообщение14.10.2025, 13:18 
Уже всего лишь 2 в степени, меньше 15200 цифр.

 
 
 
 Re: Гипотеза о симметричных простых близнецах
Сообщение14.10.2025, 14:25 
Dmitriy40 в сообщении #1705853 писал(а):
Уже всего лишь 2 в степени, меньше 15200 цифр.


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

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

 
 
 
 Re: Гипотеза о симметричных простых близнецах
Сообщение14.10.2025, 15:01 
Ryzl в сообщении #1705864 писал(а):
Т.е. не только числа Мерсенна могут быть кандидатами.
Разумеется кандидатами могут быть любые числа, лучше нечётные или даже вида $6k\pm1$ или ещё более замороченные.
Вот только числа Мерсенна выделены тем что для них есть практичный метод доказательства простоты Люка-Лемера, а для почти любых других такого метода нет. И потому числа Мерсенна можно проверить (и доказать!) на простоту гораздо большие чем почти любые другие.

 
 
 
 Re: Гипотеза о симметричных простых близнецах
Сообщение14.10.2025, 16:23 
Dmitriy40 в сообщении #1705871 писал(а):
Ryzl в сообщении #1705864 писал(а):
Т.е. не только числа Мерсенна могут быть кандидатами.
Разумеется кандидатами могут быть любые числа, лучше нечётные или даже вида $6k\pm1$ или ещё более замороченные.
Вот только числа Мерсенна выделены тем что для них есть практичный метод доказательства простоты Люка-Лемера, а для почти любых других такого метода нет. И потому числа Мерсенна можно проверить (и доказать!) на простоту гораздо большие чем почти любые другие.



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

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

 
 
 
 Re: Гипотеза о симметричных простых близнецах
Сообщение15.10.2025, 09:35 
Ryzl в сообщении #1705846 писал(а):
3 часа работы.

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

-- 15.10.2025, 09:38 --

Ryzl в сообщении #1705878 писал(а):
Понятно, что мои числа никак за обозримое время не проверить на простоту.

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

 
 
 
 Re: Гипотеза о симметричных простых близнецах
Сообщение15.10.2025, 12:23 
Да ничем они не лучше:
Код:
? 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(), что она тоже сама проверяет малые делители, а основное время тратится на проверку действительно простых, и потому последние пять вариантов фактически эквиваленты.

 
 
 
 Re: Гипотеза о симметричных простых близнецах
Сообщение16.10.2025, 14:51 
Аватара пользователя
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

 
 
 
 Re: Гипотеза о симметричных простых близнецах
Сообщение20.10.2025, 08:09 
Приветствую Всех!

Тема как-то свернула на простые числа. Хотя первоначально была цель показать правильность гипотезы Гольдбаха.

Я немного невнятно написал о вероятности отсутствия пар симметричных простых близнецов.

Если вероятность примерно равна вероятности выпадения 18000 подряд аверса монеты при бросании, то стоит ли вообще учитывать такую вероятность. Вот я про что хотел сказать.

Вот и вероятность отсутствия симметричных пар простых близнецов на диапазоне до 1 000 000 приблизительно равна вероятности выпадения 18 000 аверсов подряд при бросании монеты.

Что думаете об этом?

P.S.
Вот результат рассмотрения структуры пар от 10 до 200000

Итоговая статистика по 99996 рассмотренным диапазонам: (П- простое, С - составное)
П-С: 6-8%; П-П: 1-3,8 %; С-П: 4-8%; С-С: 80-85%
Минимальное % пар «Простое - Простое»: 1.01444%
Максимальное % пар «Простое - Простое»: 3,8%

P.S. пока распределение пар в принципе однородно, нет никаких всплесков или провалов по количеству. В процентном соотношении все значения колеблются вокруг определенных значений.

 
 
 
 Re: Гипотеза о симметричных простых близнецах
Сообщение20.10.2025, 08:56 
Аватара пользователя
Что-то туплю ;(
Так и не понял, что есть сабж. Чем симметричные простые близнецы отличаются от прочих (простых близнецов), которые не симметричные?

 
 
 
 Re: Гипотеза о симметричных простых близнецах
Сообщение20.10.2025, 09:26 
пианист в сообщении #1706464 писал(а):
Что-то туплю ;(
Так и не понял, что есть сабж. Чем симметричные простые близнецы отличаются от прочих (простых близнецов), которые не симметричные?


Просто простые числа близнецы это подмножество симметричных простых близнецов.

Например для числа 36 существует 4 пары простых симметричных близнецов (дающих в сумме 36)

[5, 31], [7, 29], [13, 23], [17, 19], Общее количество пар: 4

В этом множестве одна пара простых близнецов [17,19]

 
 
 
 Re: Гипотеза о симметричных простых близнецах
Сообщение20.10.2025, 09:42 
Ryzl в сообщении #1706460 писал(а):
Вот и вероятность отсутствия симметричных пар простых близнецов на диапазоне до 1 000 000 приблизительно равна вероятности выпадения 18 000 аверсов подряд при бросании монеты.

До $4\cdot 10^{18}$ бинарная гипотеза Гольдбаха проверена и подтверждена, сплошняком. Вероятность её справедливости на этом диапазоне -- единица.

-- 20.10.2025, 09:44 --

пианист в сообщении #1706464 писал(а):
Чем симметричные простые близнецы отличаются от прочих (простых близнецов), которые не симметричные?

Ничем :mrgreen: Любая пара натуральных нечётных (в том числе простых) чисел "симметрична" (в смысле, употребляемом ТС) относительно их полусуммы.

 
 
 
 Re: Гипотеза о симметричных простых близнецах
Сообщение20.10.2025, 09:52 
Аватара пользователя
Ryzl
А зачем тогда вообще придумывать новые термины?
Проще же так и говорить: пары нечетных простых чисел.
wrest
Ну я просто думал, что это какое-то неизвестное мне понятие, которое все участники обсуждения знают.

 
 
 
 Re: Гипотеза о симметричных простых близнецах
Сообщение20.10.2025, 09:57 
wrest в сообщении #1706468 писал(а):
Ryzl в сообщении #1706460 писал(а):
Вот и вероятность отсутствия симметричных пар простых близнецов на диапазоне до 1 000 000 приблизительно равна вероятности выпадения 18 000 аверсов подряд при бросании монеты.

До $4\cdot 10^{18}$ бинарная гипотеза Гольдбаха проверена и подтверждена, сплошняком. Вероятность её справедливости на этом диапазоне -- единица.

-- 20.10.2025, 09:44 --

пианист в сообщении #1706464 писал(а):
Чем симметричные простые близнецы отличаются от прочих (простых близнецов), которые не симметричные?

Ничем :mrgreen: Любая пара натуральных нечётных (в том числе простых) чисел "симметрична" (в смысле, употребляемом ТС) относительно их полусуммы.


У меня речь о вероятности НЕвыполнения гипотезы Гольдбаха. А Вы приводите пример проверенной вероятности выполнения гипотезы Гольдбаха.

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

-- 20.10.2025, 12:01 --

пианист в сообщении #1706470 писал(а):
Ryzl
А зачем тогда вообще придумывать новые термины?
Проще же так и говорить: пары нечетных простых чисел.
wrest
Ну я просто думал, что это какое-то неизвестное мне понятие, которое все участники обсуждения знают.



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

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

 
 
 
 Re: Гипотеза о симметричных простых близнецах
Сообщение20.10.2025, 11:29 
пианист в сообщении #1706470 писал(а):
Ну я просто думал, что это какое-то неизвестное мне понятие, которое все участники обсуждения знают.

Ну от меня потстановка задачи тоже ускользает. По сути, ТС разбивает пары простых нечётных чисел на классы эквивалентности (в класс попадают те, сумма которых равна конкретному чётному числу). Гипотеза Гольдбаха говорит о том, что для всех четных начиная с 4, эти классы не пустые. ТС теперь видимо хочет посчитать мощности этих классов с какой-то не очень ясной целью. Может он думает, что раз в экспериментах мощности в целом растут по мере роста четных чисел, то классы и подавно непустые. Ещё вроде была попытка сказать, что если мы отнимаем от чётного числа простое, то получившаяся разность имеет более высокую вероятность простоты чем случайное нечётное число близкое по величине. В общем, пока ясной формулировки чего хочет ТС -- мы не видели.

 
 
 [ Сообщений: 87 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group