Как стать автором
Обновить

Найдено 45-е простое число Мерсенна?

Занимательные задачки
Математики из распределённого проекта по поиску простых чисел GIMPS объявили, что одна из клиентских машин, которая участвует в вычислениях, передала на сервер файл с новым простым числом Мерсенна! Это важное событие для математического сообщества, потому что до сих пор было известно только 44 таких числа, последнее было найдено ровно два года назад.

Числа Мерсенна имеют вид 2n-1, где n — натуральное число. Последовательность чисел Мерсенна начинается так:
1, 3, 7, 15, 31, 63, 127, 255, 511, 1023,… (последовательность A000225 в OEIS).

Простые числа Мерсенна являются самыми большими простыми числами, известными науке. Предыдущий мировой рекорд принадлежал числу 232582657-1, имеющему 9.808.358 разрядов. О величине нового числа пока не сообщается. Его проверка идёт уже неделю на двух суперкомпьютерах, процессы завершатся 12 и 16 сентября.

Для нашедшего первое в мире число Мерсенна, которое превысит 10 млн разрядов, предусмотрен денежный приз в размере $100 тыс.

via Scientific American
Всего голосов 79: ↑69.5 и ↓9.5 +60
Просмотры 1K
Комментарии 94

простые числа

Чулан
Последние несколько недель меня не покидают мысли о простых числах. Точнее об оптимизации и параллельных вычислениях при их поиске. В итоге, проснулся я сегодня и начал кодить. В общем, разминка для ума хорошая — много идей, много чего нового узнаю в процессе их реализации. Код падает, отлаживается, ищет все большие простые числа, снова падает и т.д. А в качестве отходов остаются простые числа.
Вот, собственно и вопрос к сообществу — а что бы еще с ними сделать с этими простыми числами, кроме как использовать для поиска больших простых чисел? За любые идеи буду благодарен.
Кстати, если кому нужны простые числа — те, что прога находит лежат тут (это не реклама, если не любите ссылки — не ходите). Пока не в он-лайн режиме, но это еще одна из подзадач.
Всего голосов 12: ↑6 и ↓6 0
Просмотры 560
Комментарии 22

Параллельные вычисления при поиске простых чисел.

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

если интересно, смотрим дальше
Всего голосов 40: ↑31 и ↓9 +22
Просмотры 1.1K
Комментарии 55

Математика. Симметрия «псевдопростых близнецов»

Математика *
На досуге изучал свойства простых чисел и выявил одну возможно интересную закономерность. Поискал в Сети, по-моему, подобный вопрос прежде не поднимался.

Симметрия близнецов псевдопростых чисел
Читать дальше →
Всего голосов 99: ↑82 и ↓17 +65
Просмотры 1.4K
Комментарии 72

Волшебное решето Эратосфена

Алгоритмы *
image
Наверняка все, кто читает этот пост не раз использовали, или хотя бы слышали о решете Эратосфена — методе отыскания простых чисел. Сама проблема получения простых чисел занимает ключевое место в математике, на ней основаны некоторые криптографические алгоритмы, например RSA. Есть довольно много подходов к данной задаче, но в этой статье я остановлюсь на некоторых модификациях самого простого из них — решета Эратосфена.
Читать дальше →
Всего голосов 83: ↑74 и ↓9 +65
Просмотры 67K
Комментарии 35

Теперь у хабровчан есть своя команда в проекте GIMPS!

Алгоритмы *Математика *

Приветствую!
Наверное, многие уже слышали о проекте распределенных вычислений по поиску больших простых чисел GIMPS (Great Internet Mersenne Prime Search). На хабре уже проскакивала информация о проекте и его результатах.

Если вы из тех, кто любит разглядывать 12мегабайтные числа в поисках интересностей и просто с целью медитации, не боитесь всё время видеть 100 процентную загрузку CPU (зная, что программа работает с приоритетом «ниже среднего» и практически не влияет на быстродействие машины), а так же хотите внести свой вклад в развитие математики, то прошу под кат.
Читать дальше →
Всего голосов 37: ↑30 и ↓7 +23
Просмотры 1.1K
Комментарии 27

Принцип цикады и почему он важен для веб-дизайнеров

CSS *
Перевод
Пару лет назад я прочитал интересные факты о жизненном цикле периодических цикад. Обычно мы не видим вокруг себя много этих насекомых, потому что бóльшую часть своей жизни они проводят под землёй и тихо сосут корни растений.

Однако, в зависимости от вида, каждые 7, 11, 13 или 17 лет периодические цикады одновременно массово вылезают на свет и превращаются в шумных летающих тварей, спариваются и вскоре умирают.

Хотя наши странные цикады весело уходят в иной мир, возникает очевидный вопрос: это просто случайность, или числа 7, 11, 13 и 17 какие-то особенные?
Читать дальше →
Всего голосов 696: ↑682 и ↓14 +668
Просмотры 218K
Комментарии 119

Вычисление простых чисел на шаблонах C++

Ненормальное программирование *C++ *
В этом посте я расскажу как сделать совершенно бесполезную вещь — вычислять простые числа при помощи шаблонов C++.

Алгоритмы проиллюстрированы кодом на Scheme, поэтому осторожно: скобочки!

Читать дальше →
Всего голосов 46: ↑42 и ↓4 +38
Просмотры 19K
Комментарии 44

Алгоритм нахождения N первых простых чисел

Алгоритмы *
Из песочницы
В процессе обучения программированию я столкнулся с задачей поиска 1M первых простых чисел.

На Хабре уже не раз писали об этом. Но, чаще всего, речь шла о поиске всех простых чисел до числа N. Я же расскажу о том, как решал задачу нахождения N первых простых чисел.

На первый взгляд может показаться, что разницы в этих задачах практически нет. И это действительно так, пока мы не поймем, что перебор делителей справляется с задачей крайне плохо.

В результате проведенной работы на поиск 1 миллиона простых чисел у меня уходит всего 0,262 секунды, что, конечно же, не предел, но уже впечатляет. Алгоритм реализован на C++.

Читать дальше →
Всего голосов 27: ↑16 и ↓11 +5
Просмотры 27K
Комментарии 29

Алгоритм нахождения N первых простых чисел — Решето Аткина

Алгоритмы *
Из песочницы
В процессе реализации одной программы я столкнулся с задачей поиска простых чисел до числа N порядка 10^9. На хабре уже неоднократно писали про различные способы и методы, но не упоминали про основной метод решения, что я сегодня и постараюсь исправить.

Читать дальше
Всего голосов 14: ↑9 и ↓5 +4
Просмотры 17K
Комментарии 13

Принцип цикады в музыке или магия простых чисел (на примере PureData)

Звук
Прочитав замечательную статью на хабре об использовании простых чисел для создания не повторяющегося фона, я подумал, почему бы не реализовать подобное для генерации музыки? Поразмыслив, я решил реализовать все следующим образом. Будет создано несколько сообщений, содержащих последовательность из нулей и единиц. По сигналу из метронома из каждого сообщения будет извлекаться один единственный элемент, после чего все элементы будут суммированы. Количество элементов в сообщении будет разное, и будет представлять простое число. На выходе будет ожидаться целое число от нуля до %количество_сообщений%, которое замапится на определенную ноту.
Можно переходить к патчингу, но сначала...
Всего голосов 49: ↑48 и ↓1 +47
Просмотры 4.4K
Комментарии 23

Еще раз о поиске простых чисел

Алгоритмы *
Скульптура `Решето Эратосфена` (Стэнфордский университет) В заметке обсуждаются алгоритмы решета для поиска простых чисел. Мы подробно рассмотрим классическое решето Эратосфена, особенности его реализации на популярных языках программирования, параллелизацию и оптимизацию, а затем опишем более современное и быстрое решето Аткина. Если материал о решете Эратосфена предназначен в первую очередь уберечь новичков от регулярного хождения по граблям, то алгоритм решета Аткина ранее на Хабрахабре не описывался.

На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета
Читать дальше →
Всего голосов 159: ↑151 и ↓8 +143
Просмотры 213K
Комментарии 28

Быстрое индексное умножение по модулю

Алгоритмы *

Введение


Обычно данный материал приводится с обилием формул и рассчитан больше на математиков. Я постараюсь расписать его наиболее доступно на простых численных примерах с точки зрения применения этого метода в микроэлектронике на аппаратном уровне. В численных примерах для наглядности будет использоваться значение p = 11.

Постановка задачи


Положим, что нам требуется выполнить умножение следующего вида: res = (a*b) mod p, где
0 <= a < p
0 <= b < p
p – простое число.
mod p – операция нахождения остатка по модулю.
И выполнить его надо на низком уровне, где нет как таковой операции умножения и операции взятия остатка от деления или же они реализуются достаточно сложно (например, в электронном устройстве).
Подробности
Всего голосов 42: ↑41 и ↓1 +40
Просмотры 34K
Комментарии 23

Алгоритм Диффи — Хеллмана

Криптография *Алгоритмы *Математика *
Одна из фундаментальных проблем криптографии – безопасное общение по прослушиваемому каналу. Сообщения нужно зашифровывать и расшифровывать, но для этого обеим сторонам нужно иметь общий ключ. Если этот ключ передавать по тому же каналу, то прослушивающая сторона тоже получит его, и смысл шифрования исчезнет.

Алгоритм Диффи — Хеллмана позволяет двум сторонам получить общий секретный ключ, используя незащищенный от прослушивания, но защищённый от подмены канал связи. Полученный ключ можно использовать для обмена сообщениями с помощью симметричного шифрования.

Предлагаю ознакомиться с принципом работы алгоритма Диффи – Хеллмана в замечательном видео от Art of the Problem в моем переводе.

Всего голосов 140: ↑132 и ↓8 +124
Просмотры 161K
Комментарии 33

Простая программа на ассемблере x86: Решето Эратосфена

Assembler *
Tutorial

Вступительное слово


По своей профессии я не сталкиваюсь с низкоуровневым программированием: занимаюсь программированием на скриптовых языках. Но поскольку душа требует разнообразия, расширения горизонтов знаний или просто понимания, как работает машина на низком уровне, я занимаюсь программированием на языках, отличающихся от тех, с помощью которых зарабатываю деньги – такое у меня хобби.

И вот, я хотел бы поделиться опытом создания простой программы на языке ассемблера для процессоров семейства x86, с разбора которой можно начать свой путь в покорение низин уровней абстракции.

До ее написания я сформулировал такие требования к будущей программе:
  • Моя программа не должна быть программой под DOS. Слишком много примеров ориентировано на нее в связи с простым API. Моя программа обязательно должна была запускаться на современных ОС.
  • Программа должна использовать кучу – получать в свое распоряжение динамически распределяемую память.
  • Чтобы не быть слишком сложной, программа должна работать с целыми беззнаковыми числами без использования переносов.

Задачей для своей программы я выбрал поиск простых чисел с помощью Решета Эратосфена. В качестве ассемблера я выбрал nasm.

Код я писал с упором больше на стиль и понятность, чем на скорость его выполнения. К примеру, обнуление регистра я проводил не с помощью xor eax, eax, а с помощью mov eax, 0 в связи с более подходящей семантикой инструкции. Я решил, что поскольку программа преследует исключительно учебные цели, можно распоясаться и заниматься погоней за стилем кода в ассемблере.

Итак, посмотрим, что получилось.
Читать дальше →
Всего голосов 47: ↑40 и ↓7 +33
Просмотры 103K
Комментарии 25

Найдено 48-е простое число Мерсенна

Высокая производительность *Математика *
Математики из распределённого проекта по поиску простых чисел GIMPS объявили об обнаружении нового простого числа Мерсенна. Это важное событие для математического сообщества, потому что до сих пор было известно только 47 таких чисел, последнее было найдено в июне 2009 года.

48-е простое число Мерсенна — 257.885.161-1, с 17.425.170 десятичными разрядами. См. полную запись числа в текстовом формате.

Числа Мерсенна имеют вид 2n-1, где n — натуральное число. Простые числа Мерсенна являются самыми большими простыми числами, известными науке. Предыдущий мировой рекорд принадлежал числу 243.112.609-1, имеющему 12.978.189 десятичных разрядов.
Читать дальше →
Всего голосов 107: ↑96 и ↓11 +85
Просмотры 71K
Комментарии 140

Неизвестный математик совершил прорыв в теории простых чисел-близнецов

Математика *
В математике чрезвычайно редко случается, чтобы учёный старше 40 лет опубликовал первую серьёзную научную работу. Ещё реже бывает, чтобы эта работа имела большую научную ценность. Именно такой редчайший случай представляет из себя доцент университета Нью-Гэмпшира Итан Чжан (Yitang Zhang), который до сих не имеет ни должности профессора, ни веб-странички со списком научных работ. Тем не менее, ему удалось совершить серьёзный шаг к решению одной из старейших математических проблем — гипотезе о простых числах-близнецах.

Когда журнал “Annals of Mathematics” получил 17 апреля 2013 года научную работу Чжана, они восприняли её скептически. Заявка на прорывное исследование от неизвестного учёного? Это слишком банально и часто встречается, чтобы оказаться правдой. На удивление редколлегии, несколько научных экспертов подробно изучили работу Чжана — и нашли доказательство гипотезы о расстоянии между парными простыми числами предельно ясным, чётким и бесспорным.

В результате, журнал одобрил работу для публикации в исключительно короткие сроки — уже через три недели после поступления.
Читать дальше →
Всего голосов 232: ↑217 и ↓15 +202
Просмотры 181K
Комментарии 169

О простых числах, криптографии и повреждениях мозга

Криптография *Математика *
Сегодня же пятница, да?

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

В одном из сюжетов автор — практикующий врач, работающий с людьми с разной степенью повреждения мозга, сталкивается с близнецами-аутистами, играющими друг с другом в игру. Сначала один из них называет шестизначное число, через какое-то время другой явно этому чилу радуется, словно что-то в нем разглядев, и в свою очередь, называет другое шестизначное число. Процесс повторяется много раз.
Читать дальше →
Всего голосов 99: ↑76 и ↓23 +53
Просмотры 45K
Комментарии 66

Пять удивительных математических фактов

Математика *
Перевод
Для начала небольшой спойлер

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

Математика – одна из немногих областей знаний, которая может быть объективно названа истинной, потому что ее теоремы основаны на чистой логике. Но в то же время эти теоремы часто оказываются очень странными и противоречащими интуиции.

Некоторые люди считают математику скучной. Следующие примеры показывают, что она какая угодно, но не такая
Читать дальше →
Всего голосов 167: ↑141 и ↓26 +115
Просмотры 142K
Комментарии 271

Коллективный разум в теории чисел

Математика *
В мае на Хабре была опубликована статья, которая повествует о работе Yitang Zhang в области теории простых чисел, вызвавшей большой резонанс в научном сообществе. В этой заметке даётся краткая сводка результатов, которых удалось достичь научному сообществу спустя девять месяцев с момента публикации этой работы.

Подробности
Всего голосов 77: ↑72 и ↓5 +67
Просмотры 31K
Комментарии 33