Comments 41
Я мало что понимаю в такой математике, но выглядит круто! Вот интересно, можно ли на основании всех этих закономерностей и корелляций вывести формулу рассчёта произвольного простого числа?
Есть разные (вроде бы только эмпирические) формулы для n-го простого числа.
В теории эти закономерности позволяют сделать поиск более интеллектуальным, в том плане, что после обнаружения очередного простого числа мы будем в первую очередь будем проверять наиболее вероятные числа. К такому алгоритму стоило бы добавить эвристическую логику, которая модифицировала бы эти вероятности с удалением от предыдущего числа если вдруг существует какая-то закономерность в дистанциях между двумя простыми числами. Но на практике, полагаю, служебные потери будут слишком велики при невысокой надежности этого метода (проверять все равно надо будет все числа, которые могут быть простыми). Уверен, когда-нибудь тайну простых чисел раскроют, но не сегодня)
Очень интересно, на чем и как считал автор статьи. Когда речь заходит о 10 000 000 простых чисел 40 порядка, речь идет явно не о паре минут на домашнем процессоре)
Очень интересно, на чем и как считал автор статьи. Когда речь заходит о 10 000 000 простых чисел 40 порядка, речь идет явно не о паре минут на домашнем процессоре)
Это не так сложно, если нужны именно числа после 40 порядка (речь же о двоичной системе?), То считаем простые числа решетом Эратосфена или Аткина до, примерно, 20+ порядка все простые числа, а затем ищем одним из этих же алгоритмов числа после 40 порядка, зная распределение простых чисел, можно предположить, что нам понадобится проверить не больше 10^9. Итого, алгоритм работает за O(2^k+n*k), где k=20, n = 10000000
Могу подробнее об этом статью написать, но идея в том, что на домашнем компьютере это считается пару секунд:)
мне казалось, что речь о десятичной системе. По крайней мере это было бы логично, статья ведь не о вычислениях как таковых. В какой-то степени можно будет оптимизировать расчеты, но они будут идти уже ведь с помощью «длинной арифметики». Когда я еще в школе пытался реализовать некоторые операции, получалось очень и очень долго. Хотя тогда производительность ПК была раз в 10 ниже, да и алгоритмы наверняка не оптимальные были.
Пару секунд на одном ядре уж точно не может считаться) про 8 ядер врать не буду, но полагаю, длительность все таки на порядок выше)
Пару секунд на одном ядре уж точно не может считаться) про 8 ядер врать не буду, но полагаю, длительность все таки на порядок выше)
Вы где были последние лет 300? :)
Очень классная статья. Простые числа — вообще довольно интересная штука, помнится я когда-то сам пытался какие-то закономерности искать и вот это вот всё. И ведь нашёл кое-что такое, чего я нигде по интернетам не видел. Может кто-то более сведущий подскажет, может уже было где-то подобное? Интересно было бы почитать.
В общем, всё довольно просто. Если взять Скатерть Улама и сложить её вдоль горизонтальных или вертикальных магистралей, как лист бумаги, то можно заметить, что простые числа не накладываются друг на друга (за исключением чисел 2 и 19, если складывать по вертикальной магистрали).
На больших по размеру скатертях не проверял, но было бы интересно. Эх, вот бы найти способ сложения Скатерти Улама таким образом, чтобы пустот между простыми числами не было вообще. Гранд-мастера оригами, ау! :D
В общем, всё довольно просто. Если взять Скатерть Улама и сложить её вдоль горизонтальных или вертикальных магистралей, как лист бумаги, то можно заметить, что простые числа не накладываются друг на друга (за исключением чисел 2 и 19, если складывать по вертикальной магистрали).
Сложение вдоль вертикальной магистрали (красный пиксель - единица, желтый - наложение 2 и 19)
Сложение вдоль горизонтальной магистрали (красный пиксель - единица)
На больших по размеру скатертях не проверял, но было бы интересно. Эх, вот бы найти способ сложения Скатерти Улама таким образом, чтобы пустот между простыми числами не было вообще. Гранд-мастера оригами, ау! :D
UFO just landed and posted this here
Это логично: в скатерти Улама по четности числа образуют шахматный паттерн, поэтому при сгибании нечетные числа накладываются на четные. А так как все простые числа > 2 нечетные, то они не могут накладываться друг на друга.
Ваша закономерность объясняется довольно просто.
Наглядно
Красные — чётные, зеленые — нечётные. А так как все простые числа — нечётные, то и нет совпадений (за исключением единственного простого чётного — двойки).
Четные и нечетные числа на скатерти Улама чередуются, как клетки на шахматной доске. Если сложить ее вдоль любой вертикали или горизонтали, то черные клетки наложатся на белые, четные числа, на нечетные. Все простые, кроме 2, нечетные, отсюда и Ваш результат.
Вот интересно стало, существует ли какая-то общедоступная «база данных» всех обнаруженных простых чисел или каждый исследователь должен сам их вычислять?
Cуществуют в великом множестве, вплоть до миллионов. А есть куча списков найденных огромных простых чисел, как правило, специального вида. Вбейте последовательность простых чисел от 3 до 51 в гугл и результат вас удивит.
Как-то наткнулся на сайт с заманчивым предложением: For $19.99 you can download all prime number list up to 400 digits.
тут интереснее построить нормальность распределения следующего простого числа после 1000 000-2000 000 (что бы избежать большого изменения при малых числах)
возможно там что то типа Пуасона с математическим ожиданием n/ln(n)
возможно там что то типа Пуасона с математическим ожиданием n/ln(n)
очередная скатерть Улама.
познавательно, спасибо автору.
познавательно, спасибо автору.
Есть потрясающая книга на эту тему, «Простая одержимость». Конец только грустный, Гипотезу Римана не доказали и не опровергли.
В этом комментарии от realbtr есть интересная идея. Произведение двух соседних простых чисел определяет кандидатов для поиска следующего. Мне кажется, есть какая-то связь с описанным в статье, и там и там связано с периодами.
Есть ли название для такого преобразования? Я просто буду называть его «изгиб».
Чем-то напоминает преобразование Барроу-Уиллера (BWT)
Очень мало шансов, что два последовательных простых числа будут иметь одинаковый остаток деления на 7. Это будет только при разнице между ними 14, 28…
А чаще всего она 2 :)
А чаще всего она 2 :)
В своё время численно экспериментировал с гипотезой Гольдбаха, для чего вычислял сколькими способами можно представить каждое четное число в виде суммы двух простых. Как оказалось для праймориалов количество таких разложений заметно выше, чем для соседних. На графиках ниже стрелками отмечены праймориалы 210 и 30030 и превышение фона отчетливо видно. Для чисел, кратных праймориалом, эта тенденция тоже проявляется, но меньше.
(В подписях снизу указана половина каждого числа, т.е. там где 105 — это на самом деле 210 и т. д.).
(В подписях снизу указана половина каждого числа, т.е. там где 105 — это на самом деле 210 и т. д.).
а корреляции между радикалом и числом представлений в виде суммы простых нет?
для праймориала он равен радикалу.
для праймориала он равен радикалу.
Этого я не проверял. Но не думаю, что корреляция будет намного лучше, чем на графиках выше. Для степеней двойки например радикал равен двум, а число представлений в виде сумм двух простых (для чисел, начиная с 4 и заканчивая 8192) следующее: 1, 1, 2, 2, 5, 3, 8, 11, 22, 25, 53, 76. Для этих чисел корреляции не видно (что, конечно, не исключает того, что она может быть видна для других чисел).
может быть, изучать простые числа проще, переведя их в двоичный вид? Например, самая правая цифра будет 1 (кроме как для числа 2
Кстати есть классная программа https://github.com/kimwalisch/primesieve
Если вам нужно сгенерировать простые числа.
Я как-то решил написать программу на 10^9 строк кода генерирующую число pi использующую последовательность простых чисел. Программу написал на C она занимала несколько гигабайт и gcc отказывался её компилировать)
А вот мой генератор простых числел на C.
Как и вся высшая математика: Красива, Сложна, Безумно интересна. Однозначно хороший материал для ознакомления
Sign up to leave a comment.
Структура и случайность простых чисел