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

Попробую эту сверх-задачу ещё раз сформулировать:
maytonДавайте поставлю сверх-задачу.

Пускай задана максимально-известная prime-константа Мерсенна (Хи-мерсенна).


На каком расстоянии от Хи-Мерсенна находится следующее простое число?
Ясно, что на своих ПК мы не сможем (пока) «искать простоту» вблизи таких больших чисел.

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

Можно искать следующее простое число за , двумя способами:
- искать следующее простое число Мерсенна;
- искать следующее простое число, следующее за этим число Мерсенна.
Если для первого варианта есть тест Люка-Лемера, то для второго варианта теста простоты пока нет

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

Остаётся найти другой тест для поиска простых чисел в окрестности чисел Мерсенна, по скорости сравнимого с тестом Люка-Лемера.

maytonНам следует оставить бесполезные Попытки просто искать числа. В районе сверхбольших.
Вычислительная сложность такова что наших машин не хватит.
Давай откатывать гипотезы на малых числах которые хотя бы быстро вычислимы.Конечно, сначала проверка гипотез будет на малых числах,
и если гипотеза работает,
то, согласно эвристике, можно гипотезу в виде алгоритма распространить на большие числа.

Немного о тесте Люка-Лемера.
Как известно, числа Мерсенна получили известность благодаря тесту простоты Люка-Лемера.
Однако тест Люка-Лемера может проверять только числа из последовательности Мерсенна.
Другие большие числа этот тест не рассматривает.
Все остальные известные тесты простоты не могут в разумное время определить простоту больших чисел,
поскольку такие тесты включают в себя объём вычислений, намного больший, чем объём вычислений теста Люка-Лемера.

При определении простоты числа тест простоты Люка-Лемера формирует
последовательность чисел из (n – 2) остатков по модулю квадратов чисел, меньших n.
После того, как последовательность сформирована, оценивается последний элемент последовательности.
Если последний элемент равен числу 0, тогда число Mn простое.
Если последний элемент не равен числу 0, тогда число Mn составное.
В тесте Люка-Лемера не применяется формула Ферма, в отличие от большинства тестов простоты.
Это является преимуществом теста по быстроте.

Поэтому, если разрабатывать новый алгоритм,
то его быстродействие должно сравниться с быстродействием теста Люка-Лемера.

В эвристическом алгоритме для числа n одним из основных элементов является число d.

Появляется соблазн "сформировать" очень большие числа следующим образом.
Выбирается очень большое число 2^m, и уже для этого числа «подбирается» число d. Таким образом, получается число
2^m * d + 1

Такие числа уже рассматривались.
Они называются числами Прота.
https://ru.wikipedia.org/wiki/Число_Прота
Для проверки таких чисел на простоту существует теорема Прота
https://ru.wikipedia.org/wiki/Теорема_Прота
Данная теорема Прота является вероятностным тестом простоты.

Самым большим известным простым числом Прота является число 10223*2^31172165 + 1 ,
которое является крупнейшим известным простым числом, не являющимся числом Мерсенна.

Были проверены числа Прота на небольших числах m.
Можно для каждого значения m определить минимальное значение d.

Появилась ещё одна статья.
http://sci-article.ru/stat.php?i=1569407195

Если коротко, то
получен эвристический алгоритм для определения простых чисел Мерсенна Mn .

Составлена на Python программа с применением эвристического алгоритма по определению простых чисел Мерсенна.

Время работы такой программы сопоставимо со временем работы программы теста Люка-Лемера.

Получается, что
время определения (n – 2) квадратов чисел, меньших Mn, в виде остатков по модулю Mn
почти равно времени определения остатка по модулю Mn для числа
a^((Mn – 1)/2)
В статье рассмотрено число a = 3. Показаны возможности других оснований степени.

В отличие от теста Люка-Лемера
данный эвристический алгоритм определяет простые числа Mnk = 2^n - 1 + 4*k, где k - натуральное число.

Программа на Python подтвердила эти расчёты для n < 60 и для шагов 1 <= k <= 25.

AklinGennadiy Usov,
продолжайте наблюдения.Дальнейшие наблюдения уже почти не нужны.

1. Получен эвристический алгоритм определения всех простых чисел (проверено на диапазоне от 5 до 250 000 000) (новизна).

2. Получена последовательность простых чисел, состоящая из 50% всех простых чисел. При этом для каждого проверяемого числа достаточно 3-х раундов вычислений (новизна).

3. Получен эвристический алгоритм определения простых чисел Мерсенна, сопоставимый по времени работы с тестом Люка-Лемера.

4. Данный эвристический алгоритм можно применять для определения простых чисел в окрестности чисел Мерсенна (новизна).

maytonRange Primes Found(Usoff) Primes Found(JDK::BigInteger) Primes (theoretical) Elapsed time(s) Average Speed (primes/sec)2 - 10024002^200 + 1 - 2^200 + 1 + 1 000 0007134611892^500 + 1 - 2^500 + 1 + 200 00057622882^1024 + 1 - 2^1024 + 1 + 200 0002818352^2048 + 1 - 2^2048 + 1 + 100 000782722^4096 + 1 - 2^4096 + 1 + 50 00022950И что даёт таблица?

Не стал много считать на своём стареньком ПК, поэтому только один час:

2019-10-07-09.53.54
-простое- 1760 -s- 5
-простое- 7226 -s- 1
-простое- 7422 -s- 1
-простое- 10092 -s- 2
-простое- 10472 -s- 3
-проверка чисел от - 2^4096 + 1 -дистанция - 11000
-количество простых чисел- 5
-количество раундов - 5687
-минимальное количество раундов для числа - 1
-количество минимальных раундов - 5495
-максимальное количество раундов для числа - 38
-количество максимальных раундов - 190
-остаток- 2
2019-10-07-10.54.48

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

fkthatGennadiy Usovпроверено на диапазоне от 5 до 250 000 000250 лямов это даже до 32 бит не дотягивает. Ты вот сгенери простое число битов так хотя бы на 256. А зачем так мало? 256?

Уж лучше 500, 1500, 2500,...

В работе
http://sci-article.ru/stat.php?i=1569407195

показаны последовательности простых чисел, в которых есть следующие простые числа:

2^2370 - 1 + 4
2^2648 - 1 + 8
2^1661 - 1 + 12
2^2772 - 1 + 16
2^2810 - 1 + 20

Тут появилась одна задачка:

Пусть имеется выражение:

a mod(b)

Если в данном случае b = c + d,

то как можно представить первоначальное выражение через mod(b) и mod(c),
или через их комбинацию?

Исправляю предыдущее сообщение:

то как можно представить первоначальное выражение через mod(d) и mod(c),
или через их комбинацию?

maytonИли ты имел в виду дистрибутивность операции mod?Да.

Может быть можно получить функцию вида

x mod(c) +- y mod(d) +- (что-то),

или другие опперации?

BarlonemaytonДля умножения что-то подобное было. Или для возведения в степень. Я думаю если Барлон заскочет
в топик - то он прояснит. Вроде скилованный парень в этих кольцах и модулях.Для умножения. Китайская теорема об остатках.Получается, что есть формулы только для умножения, а для сложения формул нет.