Рубрика «простые числа» - 4

Структура и случайность простых чисел - 1

Разбросаны ли простые числа по числовой оси подобно рассеянным ветром семенам? Разумеется нет: простота — это не вопрос случайности, а результат элементарной арифметики. Число является простым тогда и только тогда, когда ни одно меньшее положительное целое число кроме единицы не делит его нацело.

Но на этом история не заканчивается. Распределение простых чисел выглядит случайным, с неравномерными разрывами и скоплениями, которые выглядят довольно хаотично. Если и существует какая-то схема, то она непостижима. На самом деле, простые числа выглядят достаточно случайными, чтобы можно было сыграть с ними в кости. Создайте список последовательных простых чисел (допустим, начав с 11, 13, 17, 19,... ) и разделите их по модулю 7. Другими словами, разделите каждое простое число на 7 и сохраните только остаток. Результатом будет последовательность целых чисел из множества {1, 2, 3, 4, 5, 6}, которая выглядит почти как результат нескольких бросков правильной кости.

$begin{align*} 11 bmod 7 & rightarrow 4 qquad 47 bmod 7 rightarrow 5 \ 13 bmod 7 & rightarrow 6 qquad 53 bmod 7 rightarrow 4 \ 17 bmod 7 & rightarrow 3 qquad 59 bmod 7 rightarrow 3 \ 19 bmod 7 & rightarrow 5 qquad 61 bmod 7 rightarrow 5 \ 23 bmod 7 & rightarrow 2 qquad 67 bmod 7 rightarrow 4 \ 29 bmod 7 & rightarrow 1 qquad 71 bmod 7 rightarrow 1 \ 31 bmod 7 & rightarrow 3 qquad 73 bmod 7 rightarrow 3 \ 37 bmod 7 & rightarrow 2 qquad 79 bmod 7 rightarrow 2 \ 41 bmod 7 & rightarrow 6 qquad 83 bmod 7 rightarrow 6 \ 43 bmod 7 & rightarrow 1 qquad 89 bmod 7 rightarrow 5 \ end{align*}$

Читать полностью »

Введение

Одним из алгоритмов для поиска простых чисел является Решето Эратосфена предложенное еще древнегреческим математиком.

Картинка из википедии:

image

Смысл в вычеркивании чисел кратных уже найденным простым. Остающиеся невычеркнутыми в свою очередь являются простыми. Более подробно расписано тут.

Одна из проблем при поиске решетом это объем памяти который надо выделить под фильтруемые числа. Вычеркнутые непростые удаляются уменьшая память, но изначально объем требуется большой.

Для решения используется сегментация (когда память выделяется по кускам) и другие ухищрения (см. тут).

Реализация алгоритма

Алгоритм внизу (написан на java) предполагает минимальный объем памяти — по сути для каждого найденного простого числа мы храним еще одно число — последнее зачеркнутое (наибольшее). Если я правильно оцениваю объем памяти ln(n) — число найденных простых.
Читать полностью »

Наткнувшись недавно на эту статью, я понял, что редко упоминаются способы вычисления факториала, отличные от банального перемножения последовательных чисел. Нужно эту ситуацию исправить.
Предлагаю рассмотреть «асимптотически наиболее быстрый» алгоритм вычисления факториала!Читать полностью »

Простые числа Мерсенна и тест Люка-Лемера - 1

Перевод поста Джона Макги (John McGee) "Mersenne Primes and the Lucas–Lehmer Test".
Код, приведенный в статье, можно скачать здесь.
Выражаю огромную благодарность Полине Сологуб за помощь в переводе и подготовке публикации


Содержание

Введение.
Теорема множителей Эйлера и Мерсенна
Люка и Лемер
От ${M_{13}}$ до ${M_{20}}$
Совершенные числа
21-е, 22-е и 23-е числа Мерсенна
24-е, 25-е и 26-е числа Мерсенна.
27-е и 28-е числа Мерсенна
29-е число Мерсенна
30-е и 31-е числа Мерсенна
Великий интернет-поиск чисел Мерсенна
Факторизация чисел Мерсенна


Введение.

Простое число Мерсенна — простое число вида ${M_p}={2^p} - 1$ (значение степени р также должно быть простым). Эти простые числа получили свое название от имени французского математика и религиозного ученого Мерсенна, который и составил данный список простых чисел этой формы в первой половине семнадцатого века. Первые четыре из них были известны уже давно: ${M_2}=3$, ${M_3}=7$, ${M_5}=31$ и ${M_7}=127$.

Мерсенн утверждал, что значение ${2^p} - 1$ будет простым для простых чисел $p leqslant 257$, принадлежащих множеству $p in left{ {{text{2}}{text{,3}}{text{,5}}{text{,7}}{text{,13}}{text{,17}}{text{,19}}{text{,31}}{text{,67}}{text{,127}}{text{,257}}} right}$. Во всем ли он был прав, можно проверить с помощью функции Wolfram LanguagePrimeQ, в которой используются современные методы тестирования чисел на простоту, для которых не требуется поиска конкретного множителя, чтобы доказать, что число составное.
Читать полностью »

2017 это не просто простое число… - 1

Прощай, год 2016-й. Здравствуй, год 2017-й.

Все мы знаем, что число 2017 простое (это же Гиктаймс, не так ли). Но оно гораздо больше, чем просто простое число.Читать полностью »

Специальные простые числа помогают пассивно прослушать протокол обмена ключами Диффи-Хеллмана - 1
Слайд из презентации АНБ

В 2013 году благодаря Эдварду Сноудену в СМИ попали документы АНБ. Среди них — замыленный слайд из презентации, который указывал на возможности АНБ по расшифровке трафика VPN. У АНБ не было причин врать в засекреченной презентации, так что специалисты восприняли эту информацию как свидетельство наличия некоей фундаментальной уязвимости в современных системах криптографии с открытым ключом.
Читать полностью »

В сентябре 2016 прошел очередной ежегодный отбор молодых специалистов, студентов и выпускников инженерных и математических специальностей в школу программистов HeadHunter.

Для поступления предлагалось пройти несколько этапов, решая логические/математические задачи.
Варианты решения некоторых типовых задач первого этапа я и попытаюсь разобрать в данной статье.
PS: Для удобства быстрого написания и отладки кода подсчетов использовался JavaScript.

Пока писал статью, смотрю, в песочнице меня уже опередили по теме. Однако, у меня рассмотрены другие типы задач, только одна совпала про степени (но, судя по комментариям, не в обиду автору — решение неверное).
Читать полностью »

Красота чисел. Антипростые числа - 1
У числа 60 двенадцать делителей: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

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

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199…

Все остальные натуральные числа больше единицы, которые не являются простыми, называются составными. У них несколько делителей. Так вот, среди составных чисел выделяется особая группа чисел, которые можно назвать «суперсоставными» или «антипростыми», потому что у них особенно много делителей. Такие числа всегда являются избыточными.
Читать полностью »

Математик оптимизировал решето Эратосфена, чтобы искать простые числа с меньшим расходом памяти - 1
38-летний перуанский математик Харальд Хельфготт три года назад доказал тернарную гипотезу Гольдбаха, а сейчас сумел оптимизировать компьютерный алгоритм для расчёта решета Эратосфена. Фото: Matías Loewy

В III в. до нашей эры древнегреческий математик, астроном, географ, филолог и поэт Эратосфен Киренский придумал гениальный способ поиска простых чисел. Очень эффективный и быстрый метод, который используется до сих пор, получил название решето Эратосфена.

Суть понятна из названия. Решето Эратосфена означает поиск простых чисел методом исключения. Берём список чисел, исключаем из него все составные числа — и получаем список простых чисел, словно просеяв список через решето.
Читать полностью »

image

Два математика из Стэнфордского Университета, Каннан Соундараджан [Kannan Soundararajan] и Роберт Лемке Оливер [Robert Lemke Oliver] (на фото выше) обнаружили ранее неизвестное свойство простых чисел. Выяснилось, что шансы на то, что за простым числом, оканчивающимся на 9, будет следовать число, оканчивающееся на 1, на 65% больше, чем шансы, что за ним будет следовать число, снова оканчивающееся на 9. Это предположение было численно проверено компьютерными методами для миллиардов известных простых чисел.

По словам Кена Оно, математика из Университета Эмори в Атланте, это предположение по сути противоречит ожиданиям большинства математиков. Ранее считалось, что простые числа в массе своей ведут себя достаточно случайно. Большинство теоретиков сошлось бы на предположении, что шансы иметь на конце одну из возможных для простых чисел цифр (1, 3, 7, 9) примерно равны для всех таких чисел.

Эндрю Грэнвиль [Andrew Granville] из Монреальского университета, заявил, что «мы занимаемся изучением простых чисел уже очень давно, и никто раньше этого не замечал. Это безумие какое-то. Не могу поверить, что кто-то смог до этого додуматься. Это выглядит очень странно».
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js