Comments 17
... зачем искать самое большое?
Еще для вознаграждения https://www.mersenne.org/why_join/
Отличная группа, кстати
"Так как эта задача не сулит никакой экономической или политической выгоды"
Ничего, что это фактически майнинг?
Картина Антона Фролова сразу напомнила о ВК посте "Постоянная Эйлера-Маскерони, простые числа и византийский футуризм". https://vk.com/wall-186208863_42151
А для криптографии простые числа на вес золота. Так что не такое уж это занятие и бесполезное 😅👏
А нельзя ли обучить нейросеть, чтобы она вывела формулу получения простого числа по порядку?
Нейросети здесь совершенно неприменимы, поскольку простые числа являются абсолютно детерминированными объектами. Настолько детерминированными, что не зависят ни от каких законов природы. Точно те же самые простые числа существуют в любой другой Вселенной, если там вообще могут существовать порядковые числительные.
Да и вообще, в задаче нахождения следующего простого числа или простого числа определённого размера нет никакой математической сложности — достаточно взять случайное нечётное число нужного размера и прибавлять к нему 2. В среднем через логарифм шагов мы найдём простое. Беда лишь в том, что в случае простых из Top 20, логарифм шагов — это миллион шагов. На практике используют более быстрые подходы.
Беда в том, что для простых чисел нет таких формул, это строго доказано. Есть два варианта, насколько я знаю:
1) В формуле неявно(или даже явно) нужно заложить все простые, грубо говоря, чтобы выдать n-ное простое такой формулой нужно уже знать n-ное простое.
2) Существуют многочлены огромной степени от пары десятков переменных, множество положительных значений которых совпадает с множеством простых чисел. Но там вычислительная проблема, ещё никто не нашёл хоть одного положительного значения и скорее всего не найдёт.
Блин, думал щас алгоритмами будут меряться.
Существует отличная формула, которая сразу показывает, что число простое.
Перемножаешь все числа от 
до 
, добавляешь единицу и если результат без остатка делится на 
, то число простое. Или, если на последний множитель не домножать, остаток будет единица.
Это теорема Вильсона 
Теорема доказывается на ходу: если число простое, то множители факториала можно разбить на пары, каждая из которых при перемножении её элементов даёт остаток единица, и при перемножении таких пар остаётся единица. А если число не простое, то факториал будет содержать множители числа и значит, будет кратным и значит, остаток будет ноль. Ну, кроме четвёрки, у неё остаток получается 2.
Можно даже график построить:
Жаль, что перемножить сразу все варианты чисел из миллиона бит пока как-то сложновато.
не имеющее практического применения (во всяком случае, в ближайшие тысячу лет),
Про тысячу лет слова конечно громкие слишком. Харди, насколько помню, утверждал, что рад заниматься ТЧ тк её невозможно применить к войне. Сколько там лет потребовалось, чтобы всё изменилось? Пару десятков :)
52-е по порядку нахождения https://www.mersenneforum.org/node/1055976?p=1056357#post1056357
Большие простые числа: теория и практика их поиска