Я мало что понимаю в такой математике, но выглядит круто! Вот интересно, можно ли на основании всех этих закономерностей и корелляций вывести формулу рассчёта произвольного простого числа?

Есть разные (вроде бы только эмпирические) формулы для n-го простого числа.

Насколько я знаю, они не универсальные – действуют только для некоторых простых чисел.

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

Очень интересно, на чем и как считал автор статьи. Когда речь заходит о 10 000 000 простых чисел 40 порядка, речь идет явно не о паре минут на домашнем процессоре)

Это не так сложно, если нужны именно числа после 40 порядка (речь же о двоичной системе?), То считаем простые числа решетом Эратосфена или Аткина до, примерно, 20+ порядка все простые числа, а затем ищем одним из этих же алгоритмов числа после 40 порядка, зная распределение простых чисел, можно предположить, что нам понадобится проверить не больше 10^9. Итого, алгоритм работает за O(2^k+n*k), где k=20, n = 10000000
Могу подробнее об этом статью написать, но идея в том, что на домашнем компьютере это считается пару секунд:)

мне казалось, что речь о десятичной системе. По крайней мере это было бы логично, статья ведь не о вычислениях как таковых. В какой-то степени можно будет оптимизировать расчеты, но они будут идти уже ведь с помощью «длинной арифметики». Когда я еще в школе пытался реализовать некоторые операции, получалось очень и очень долго. Хотя тогда производительность ПК была раз в 10 ниже, да и алгоритмы наверняка не оптимальные были.
Пару секунд на одном ядре уж точно не может считаться) про 8 ядер врать не буду, но полагаю, длительность все таки на порядок выше)
Да, согласен, я все неправильно посчитал)
Очень классная статья. Простые числа — вообще довольно интересная штука, помнится я когда-то сам пытался какие-то закономерности искать и вот это вот всё. И ведь нашёл кое-что такое, чего я нигде по интернетам не видел. Может кто-то более сведущий подскажет, может уже было где-то подобное? Интересно было бы почитать.

В общем, всё довольно просто. Если взять Скатерть Улама и сложить её вдоль горизонтальных или вертикальных магистралей, как лист бумаги, то можно заметить, что простые числа не накладываются друг на друга (за исключением чисел 2 и 19, если складывать по вертикальной магистрали).

Сложение вдоль вертикальной магистрали (красный пиксель - единица, желтый - наложение 2 и 19)
image


Сложение вдоль горизонтальной магистрали (красный пиксель - единица)
image


На больших по размеру скатертях не проверял, но было бы интересно. Эх, вот бы найти способ сложения Скатерти Улама таким образом, чтобы пустот между простыми числами не было вообще. Гранд-мастера оригами, ау! :D
Это логично: в скатерти Улама по четности числа образуют шахматный паттерн, поэтому при сгибании нечетные числа накладываются на четные. А так как все простые числа > 2 нечетные, то они не могут накладываться друг на друга.
Ваша закономерность объясняется довольно просто.
Наглядно
Красные — чётные, зеленые — нечётные. А так как все простые числа — нечётные, то и нет совпадений (за исключением единственного простого чётного — двойки).
image
Четные и нечетные числа на скатерти Улама чередуются, как клетки на шахматной доске. Если сложить ее вдоль любой вертикали или горизонтали, то черные клетки наложатся на белые, четные числа, на нечетные. Все простые, кроме 2, нечетные, отсюда и Ваш результат.
Вот интересно стало, существует ли какая-то общедоступная «база данных» всех обнаруженных простых чисел или каждый исследователь должен сам их вычислять?
Cуществуют в великом множестве, вплоть до миллионов. А есть куча списков найденных огромных простых чисел, как правило, специального вида. Вбейте последовательность простых чисел от 3 до 51 в гугл и результат вас удивит.
А если вбить от 3 до 8527 то гугл выдаст специальный результат-пасхалку.
У вас тоньше троллинг. По крайней мере число 8527 таки действительно простое (в отличие от 51).
Как-то наткнулся на сайт с заманчивым предложением: For $19.99 you can download all prime number list up to 400 digits.
хмм, а я число пи бесплатно скачивал, до сих пор раздаю. Если кому надо, ищите на торрентах
Число Пи полностью скачали, или всё ещё докачиваете?)
9 серий первого сезона) их же раздаю)
тут интереснее построить нормальность распределения следующего простого числа после 1000 000-2000 000 (что бы избежать большого изменения при малых числах)
возможно там что то типа Пуасона с математическим ожиданием n/ln(n)
А еще лучше рассмотреть по праймориалу(2*3*5*7*11*13).
очередная скатерть Улама.
познавательно, спасибо автору.
Есть потрясающая книга на эту тему, «Простая одержимость». Конец только грустный, Гипотезу Римана не доказали и не опровергли.
Да, книга отличная. И Семихатов конечно классный переводчик.
В этом комментарии от realbtr есть интересная идея. Произведение двух соседних простых чисел определяет кандидатов для поиска следующего. Мне кажется, есть какая-то связь с описанным в статье, и там и там связано с периодами.
Есть ли название для такого преобразования? Я просто буду называть его «изгиб».

Чем-то напоминает преобразование Барроу-Уиллера (BWT)
Очень мало шансов, что два последовательных простых числа будут иметь одинаковый остаток деления на 7. Это будет только при разнице между ними 14, 28…
А чаще всего она 2 :)
В своё время численно экспериментировал с гипотезой Гольдбаха, для чего вычислял сколькими способами можно представить каждое четное число в виде суммы двух простых. Как оказалось для праймориалов количество таких разложений заметно выше, чем для соседних. На графиках ниже стрелками отмечены праймориалы 210 и 30030 и превышение фона отчетливо видно. Для чисел, кратных праймориалом, эта тенденция тоже проявляется, но меньше.


(В подписях снизу указана половина каждого числа, т.е. там где 105 — это на самом деле 210 и т. д.).
а корреляции между радикалом и числом представлений в виде суммы простых нет?
для праймориала он равен радикалу.
Этого я не проверял. Но не думаю, что корреляция будет намного лучше, чем на графиках выше. Для степеней двойки например радикал равен двум, а число представлений в виде сумм двух простых (для чисел, начиная с 4 и заканчивая 8192) следующее: 1, 1, 2, 2, 5, 3, 8, 11, 22, 25, 53, 76. Для этих чисел корреляции не видно (что, конечно, не исключает того, что она может быть видна для других чисел).
Гипотеза в следующем. Если радикал сильно меньше числа, то количество представлений в виде суммы простых будет меньше окружающих, а для состоящих из произведений простых в первой степени максимально.
может быть, изучать простые числа проще, переведя их в двоичный вид? Например, самая правая цифра будет 1 (кроме как для числа 2

При любом основании >= 2 будет не более одного простого числа, запись которого заканчивается на 0. Этот факт не дает почти ничего.
Можно посмотреть как простые числа записываются в Фиббоначиевой СС.

ну тогда самую правую цифру в двоичной записи простых чисел, больших 2, можно отбросить и изучать N-1, где N — простое.
точнее, (N-1)/2 для простых N>2

Кстати есть классная программа https://github.com/kimwalisch/primesieve
Если вам нужно сгенерировать простые числа.


Я как-то решил написать программу на 10^9 строк кода генерирующую число pi использующую последовательность простых чисел. Программу написал на C она занимала несколько гигабайт и gcc отказывался её компилировать)

Только полноправные пользователи могут оставлять комментарии.
Войдите, пожалуйста.