Поиск простого числа по новому

[Побережный Александр]

Предлагаю для поиска нового простого числа свой алгоритм.

Праймориал $p_n\#$ это произведение первых $n$ простых чисел.
Для поиска простого числа используется следующее утверждение.

Для любого фиксированного $p_n$ (простое число)
конечная последовательность $\frac{p_n\#}2\pm2^m$ содержит хотя бы одно простое число, для различных $m$.

Более общее утверждение звучит так:
Для любого фиксированного $p_n$ (простое число)
конечная последовательность $\frac{p_n\#}2\pm2^mP$ содержит хотя бы одно простое число, где $P$ - простое число или произведение простых чисел больших $p_n$.

Проверял до $101\#$. Вроде все работает.

[Someone]

Собственно, возможность искать простые числа в арифметических прогрессиях следует из теоремы Дирихле о простых числах в арифметической прогрессии. Сам метод широко используется для поиска очень больших простых чисел. Посмотрите сайт http://primes.utm.edu/ вообще и список $5\,000$ самых больших известных простых чисел на этом сайте (список непрерывно корректируется) в частности.

[Dmitriy40]

Побережный Александр в сообщении #1313387 писал(а):

Для любого фиксированного $p_n$ (простое число)

Кажется не только для простых, вообще для любых. До $300\#$ исключений не нашёл (а это уже числа более 830 знаков), хотя например для $206\#$ уже требуется $m=278$ и $m=323$ для $280\#$.

[Побережный Александр]

Уважаемый Someone, в теореме Дирихле рассматриваются бесконечные арифметические прогрессии. Я же предлагаю рассматривать конечные последовательности и вполне конкретный алгоритм нахождения. Может я вас не правильно понял, но в своих рассуждениях я на теорему Дирихле не опирался

-- Вс май 20, 2018 20:56:46 --

Уважаемый Dmitriy40, хотел бы знать, вы при проверке рассматривали выражение со знаком "плюс"?

[Someone]

Побережный Александр в сообщении #1313732 писал(а):

Я же предлагаю рассматривать конечные последовательности и вполне конкретный алгоритм нахождения.

Какие "конечные"? $\frac 12p_n\#\pm 2^m$ и $\frac 12p_n\#\pm 2^mP$? Сколько в них членов? Какие значения могут принимать $m$, $n$? Вы ничего об этом не говорили.
Но Вы правы, это не арифметическая прогрессия. Для поиска простых чисел это хуже, так как существенно быстрее растёт.

[Побережный Александр]

Число $n$ выбирается произвольно и оно фиксируется. Теперь для конкретного $n$ рассматриваются только те $m$, для которых выполняется условие $\frac12p_n\#>2^mP$, поскольку рассматриваются натуральные числа. Отсюда и конечность $m$.

[Someone]

Какие преимущества имеет ваш метод по сравнению с поиском в арифметических прогрессиях?

-- Вс май 20, 2018 21:52:36 --

Насколько большие простые числа Вы собираетесь искать таким методом?

[Побережный Александр]

Как я представляю, преимущества следующие:
1. Рассматриваются конечные последовательности, в силу ограниченности $m$.
2. Рассматривается не перебор с каким-то фиксированным шагом (арифметическая прогрессия), а скорее геометрическая прогрессия $2^m$.
3. Всегда результатом алгоритма будет простое число больше $p_n$.
4. В работе алгоритма не требуется конкретно разложить число на множители. Достаточно знать, что оно составное, чтобы алгоритм работал дальше. А раз так, то можно работать с очень большими числами.

[yk2ru]

А проверка простоты каким способом будет проводиться? Для больших чисел Мерсенна даже быстрый тест Люка-Лемера занимает много времени. У вас десятки лет будут уходить на расчёты при достаточно больших числах.

[Someone]

Побережный Александр в сообщении #1313743 писал(а):

Как я представляю, преимущества следующие:

Судя по списку, Вы не имеете никакого представления о существующих методах поиска простых чисел и проверки чисел на простоту.
1) Вообще непонятно, в чём состоит преимущество. Никто же не запрещает рассматривать только конечную часть какой-то последовательности.
2) Геометрическая прогрессия хуже арифметической, так как быстрее растёт, и поэтому шансы обнаружить простое число уменьшаются. Более того, существуют такие числа $k$, что в последовательности $k\cdot 2^n+1$ нет ни одного простого числа.
3) Тоже непонятное преимущество. Для нужд криптографии, например, ищутся простые числа в заданном промежутке. Непонятно, почему для этого ваш метод лучше любого другого.
4) Почему Вы думаете, что для поиска простых чисел в других последовательностях полное разложение числа на множители необходимо?

Вы бы покопались на сайте http://primes.utm.edu/. Там можно найти много информации о проверке чисел на простоту и о поиске больших простых чисел.

[grizzly]

Побережный Александр
Вы зря настаиваете на использовании Вашей гипотезы для практического поиска больших простых чисел. Лучше остановиться на теоретической составляющей гипотезы. Она утверждает, что в заданном конечном множестве чисел содержится простое число. Множество достаточно редкое, как уже было отмечено. Гипотеза выглядит любопытной, но я не думаю, что она верна. То, что она выполнена для небольших $n$, не особо удивляет -- ведь мы рассматриваем весьма подходящие кандидаты (особенно, если использовать знак минус). Но я сомневаюсь, что она верна даже для последовательности, продлённой до бесконечности. Хотя наблюдение интересное и опровергнуть (тем более доказать) его вряд ли будет просто.

[Dmitriy40]

Побережный Александр в сообщении #1313732 писал(а):

вы при проверке рассматривали выражение со знаком "плюс"?

Рассматривал.

Побережный Александр в сообщении #1313743 писал(а):

3. Всегда результатом алгоритма будет простое число больше $p_n$.

Тут не понял, у меня часто первым находилось число меньшее $p_n$, ведь в формуле есть и минус тоже. Правда все $m$ я не проверял, лишь до первого простого, может их там и больше одного, в том числе и всегда есть и больше. Но это стоит доказывать!

Someone в сообщении #1313756 писал(а):

Судя по списку, Вы не имеете никакого представления о существующих методах поиска простых чисел и проверки чисел на простоту.

Присоединяюсь, с добавлением "... и о целях такого поиска".

Чисто математическую ценность гипотезы оценить не могу, но на мой дилетантский взгляд она не кажется высокой.

Задумался, а есть ли вообще исключения, ведь с ростом $n$ интервалы между простыми растут быстрее чем растёт длина последовательности, значит если не попадаем по какой-то причине обязательно на простые, то должен наступить момент исключения ... Как бы это проверить-то, для тысячезначных чисел PARI/GP уже тормозит, а искать (тем более писать) спецпрогу лень ... Запущу-ка PARI/GP часиков на N-цать, посмотрим.

-- 21.05.2018, 07:18 --

А пока он уже насчитал что при $n<550$ исключений нет, причём проверяю лишь плюс в формуле (как более интересный вариант), да с ограничением на $m$.
Максимальное найденное $m: p_{513}\#/2+2^{1510}$ (на всякий случай, произведение первых 513-ти простых чисел пополам плюс 2 в 1510-й степени, всего порядка 1565 знаков).

[grizzly]

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

да с ограничением на $m$

Правильно ли я понимаю, что Вы ищете простые числа указанного вида в интервале $(p_{n}\#/2;p_{n}\#)?$

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

Чисто математическую ценность гипотезы оценить не могу, но на мой дилетантский взгляд она не кажется высокой.

На мой (не менее дилетантский :) взгляд "конечная" гипотеза была бы весьма ценной, если бы была верна (во что я нисколько не верю) и даже "бесконечная" тоже кажется очень интересной.

[Dmitriy40]

grizzly в сообщении #1313787 писал(а):

Правильно ли я понимаю, что Вы ищете простые числа указанного вида в интервале $(p_{n}\#/2;p_{n}\#)?$

Да.

Проверено до $n=1000$, исключений не найдено. Останавливаю, ждать надоело, считает уже ужасно медленно. Максимальное $m: p_{989}\#/2+2^{2756}$, почти 3350 цифр.

grizzly в сообщении #1313787 писал(а):

На мой (не менее дилетантский :) взгляд

Вам безусловно виднее, я ориентировался скорее на неконструктивность гипотезы ("простые всегда есть, но какое из них - не скажу").
Плюс поиск вон того длинного $m$ занял 16 минут, а поиск следующего простого за ним 2.3 минуты. Т.е. даже для чисел с тремя тысячами цифр интервалы между простыми невелики и быстрее найти следующее простое, чем проверять эту последовательность. Конечно это лишь грубая прикидка, но набирать статистику лень.

[grizzly]

Dmitriy40
Спасибо. Не думаю, что есть смысл искать исключения, но скорость, с которой Вы это делаете впечатляет :)

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

я ориентировался скорее на неконструктивность гипотезы ("простые всегда есть, но какое из них - не скажу").
Плюс поиск вон того длинного $m$ занял 16 минут, а поиск следующего простого за ним 2.3 минуты. Т.е. даже для чисел с тремя тысячами цифр интервалы между простыми невелики и быстрее найти следующее простое, чем проверять эту последовательность.

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