Привет! Однажды утром мне пришла в голову идея находить "исключающее ИЛИ" между координатами точки пространства и проверять полученное число на простоту. Результат такого простого алгоритма вы можете видеть на картинке. Подробнее под катом.
Читать полностью »
Рубрика «простые числа» - 3
Бесконечный узор на основе простых чисел
2018-07-22 в 16:08, admin, рубрики: Алгоритмы, бесконечность, математика, ненормальное программирование, Программирование, простые числа, процедурная генерация, процедурная генерация карт, фракталы, фрактальные ландшафтыКомпрессия больших массивов простых чисел
2018-07-21 в 7:30, admin, рубрики: C, компрессия данных, математика, простые числа, сжатие данных, теория чисел
Свойства простых чисел редко позволяют работать с ними иначе, чем в виде заранее вычисленного массива — и желательно как можно более объемного. Естественный формат хранения в виде целых чисел той или иной разрядности страдает при этом некоторыми недостатками, которые становятся существенными при росте объема данных.
Так, формат 16-разрядных беззнаковых целых при размере такой таблицы около 13 килобайт вмещает всего лишь 6542 простых числа: вслед за числом 65531 идут значения более высокой разрядности. Такая таблица годится разве что в качестве игрушки.
Наиболее ходовой в программировании формат 32-разрядных целых выглядит значительно солиднее — он позволяет хранить около 203 млн простых. Но такая таблица занимает уже около 775 мегабайт.
Еще больше перспектив у 64-разрядного формата. Однако при теоретической мощности порядка 1e+19 значений, таблица имела бы размер 64 экзабайта.
Геометрия данных 6. Физика и математика
2017-11-03 в 11:07, admin, рубрики: барицентрические координаты, время, дзета-функция Римана, Дистанционные координаты, математика, простые числа, псевдоевклидово пространствоЭто заключительная статья серии о ди- и би-координатах. В размашистом и свободном стиле покажем, как введенные понятия можно использовать для исследования данных. Конкретно обратимся к теории чисел — это хорошее поле для демонстрации идей как математики, так и физики.
Физика — почему пространство-время псевдоевклидово?
Особенность дистанционных координат в том, что лежащее в их основе понятие дистанции (квадрата расстояния) между объектами играет ключевую роль в свойствах окружающего нас мира.
Читать полностью »
Структура и случайность простых чисел
2017-10-20 в 8:04, admin, рубрики: визуализация данных, деление с остатком, математика, простые числа
Разбросаны ли простые числа по числовой оси подобно рассеянным ветром семенам? Разумеется нет: простота — это не вопрос случайности, а результат элементарной арифметики. Число является простым тогда и только тогда, когда ни одно меньшее положительное целое число кроме единицы не делит его нацело.
Но на этом история не заканчивается. Распределение простых чисел выглядит случайным, с неравномерными разрывами и скоплениями, которые выглядят довольно хаотично. Если и существует какая-то схема, то она непостижима. На самом деле, простые числа выглядят достаточно случайными, чтобы можно было сыграть с ними в кости. Создайте список последовательных простых чисел (допустим, начав с 11, 13, 17, 19,... ) и разделите их по модулю 7. Другими словами, разделите каждое простое число на 7 и сохраните только остаток. Результатом будет последовательность целых чисел из множества {1, 2, 3, 4, 5, 6}, которая выглядит почти как результат нескольких бросков правильной кости.
Решето Эратосфена, попытка минимизировать память
2017-07-14 в 14:08, admin, рубрики: Алгоритмы, простые числа, решето ЭратосфенаВведение
Одним из алгоритмов для поиска простых чисел является Решето Эратосфена предложенное еще древнегреческим математиком.
Картинка из википедии:
Смысл в вычеркивании чисел кратных уже найденным простым. Остающиеся невычеркнутыми в свою очередь являются простыми. Более подробно расписано тут.
Одна из проблем при поиске решетом это объем памяти который надо выделить под фильтруемые числа. Вычеркнутые непростые удаляются уменьшая память, но изначально объем требуется большой.
Для решения используется сегментация (когда память выделяется по кускам) и другие ухищрения (см. тут).
Реализация алгоритма
Алгоритм внизу (написан на java) предполагает минимальный объем памяти — по сути для каждого найденного простого числа мы храним еще одно число — последнее зачеркнутое (наибольшее). Если я правильно оцениваю объем памяти ln(n) — число найденных простых.
Читать полностью »
Быстрое вычисление факториала — PrimeSwing
2017-04-28 в 21:03, admin, рубрики: primeswing, Алгоритмы, математика, простые числа, факториал, факторизация, метки: primeswing, факториалНаткнувшись недавно на эту статью, я понял, что редко упоминаются способы вычисления факториала, отличные от банального перемножения последовательных чисел. Нужно эту ситуацию исправить.
Предлагаю рассмотреть «асимптотически наиболее быстрый» алгоритм вычисления факториала!Читать полностью »
Простые числа Мерсенна и тест Люка-Лемера
2017-04-25 в 13:17, admin, рубрики: wolfram language, wolfram mathematica, Алгоритмы, Блог компании Wolfram Research, Занимательные задачки, математика, Программирование, простые числа, совершенные числа, факторизация чисел, числа мерсенна
Перевод поста Джона Макги (John McGee) "Mersenne Primes and the Lucas–Lehmer Test".
Код, приведенный в статье, можно скачать здесь.
Выражаю огромную благодарность Полине Сологуб за помощь в переводе и подготовке публикации
Содержание
— Введение.
— Теорема множителей Эйлера и Мерсенна
— Люка и Лемер
— От 
до 
— Совершенные числа
— 21-е, 22-е и 23-е числа Мерсенна
— 24-е, 25-е и 26-е числа Мерсенна.
— 27-е и 28-е числа Мерсенна
— 29-е число Мерсенна
— 30-е и 31-е числа Мерсенна
— Великий интернет-поиск чисел Мерсенна
— Факторизация чисел Мерсенна
Введение.
Простое число Мерсенна — простое число вида 
(значение степени р также должно быть простым). Эти простые числа получили свое название от имени французского математика и религиозного ученого Мерсенна, который и составил данный список простых чисел этой формы в первой половине семнадцатого века. Первые четыре из них были известны уже давно: 
, 
, 
и 
.
Мерсенн утверждал, что значение 
будет простым для простых чисел 
, принадлежащих множеству 
. Во всем ли он был прав, можно проверить с помощью функции Wolfram Language — PrimeQ, в которой используются современные методы тестирования чисел на простоту, для которых не требуется поиска конкретного множителя, чтобы доказать, что число составное.
Читать полностью »
2017 это не просто простое число…
2017-01-01 в 12:22, admin, рубрики: 2017, математика, мозг, Научно-популярное, нумерология, простые числа
Прощай, год 2016-й. Здравствуй, год 2017-й.
Все мы знаем, что число 2017 простое (это же Гиктаймс, не так ли). Но оно гораздо больше, чем просто простое число.Читать полностью »
Специальные простые числа помогают пассивно прослушать протокол обмена ключами Диффи-Хеллмана
2016-10-13 в 17:06, admin, рубрики: дискретный логарифм, информационная безопасность, конечные поля, криптография, математика, модуль p, простые числа, протокол Диффи-Хеллмана
Слайд из презентации АНБ
В 2013 году благодаря Эдварду Сноудену в СМИ попали документы АНБ. Среди них — замыленный слайд из презентации, который указывал на возможности АНБ по расшифровке трафика VPN. У АНБ не было причин врать в засекреченной презентации, так что специалисты восприняли эту информацию как свидетельство наличия некоей фундаментальной уязвимости в современных системах криптографии с открытым ключом.
Читать полностью »
Разбор задач первого этапа отбора в школу программистов HeadHunter 2016
2016-10-11 в 10:21, admin, рубрики: headhunter, javascript, Алгоритмы, задачи для программистов, Занимательные задачки, простые числаВ сентябре 2016 прошел очередной ежегодный отбор молодых специалистов, студентов и выпускников инженерных и математических специальностей в школу программистов HeadHunter.
Для поступления предлагалось пройти несколько этапов, решая логические/математические задачи.
Варианты решения некоторых типовых задач первого этапа я и попытаюсь разобрать в данной статье.
PS: Для удобства быстрого написания и отладки кода подсчетов использовался JavaScript.
Пока писал статью, смотрю, в песочнице меня уже опередили по теме. Однако, у меня рассмотрены другие типы задач, только одна совпала про степени (но, судя по комментариям, не в обиду автору — решение неверное).
Читать полностью »