В предыдущих сериях мы взглянули на дробные числа с несколько необычных ракурсов. В этой серии, после введения и некоторой теоретической базы, попробуем собрать всё в удобном виде и получить пользу от имеющейся информации.
Читать полностью »
Рубрика «простые числа» - 2
Просто деление, или как создать математическую теорию и заработать на этом 400К$. Серия третья, заключительная
2019-09-14 в 17:18, admin, рубрики: делимость, квантовые алгоритмы, математика, Научно-популярное, поиск простых, простые числа, теория делимостиРешето Сундарама в сети представлено большим количеством источников краткой справочной информации. Тем не менее, я решил изложить то, что хотел бы прочитать сам в начале изучения теоретико-числовых алгоритмов.
Решето Сундарама входит в тройку известнейших методов генерации простых чисел. Сейчас к нему принято относиться как к некоторой экзотике по причине плохой вычислительной сложности: O(N(logN)). Однако асимптотика – асимптотикой, а на практике в 32-битном диапазоне просеивания Аткин, например, перегоняет Сундарама только при тщательной оптимизации.
Реализации решета Аткина, имеющие хождение в интернете, не превосходят решето Сундарама ни по временным характеристикам, ни по эффективности использования памяти. Так что метод Сундарама вполне можно использовать как вспомогательный инструмент при экспериментах с более продвинутыми алгоритмами.
Читать полностью »
Доступное объяснение гипотезы Римана
2019-05-24 в 4:56, admin, рубрики: дзета-функция Римана, математика, Научно-популярное, произведение эйлера, простые числа, распределение простых чисел
Посвящается памяти Джона Форбса Нэша-младшего
Вы ведь помните, что такое «простые числа»? Эти числа не делятся ни на какие другие, кроме самих себя и 1. А теперь я задам вопрос, которому уже 3000 лет:
- 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, p. Чему равно p? 31. Каким будет следующее p? 37. А следующее p ? 41. А следующее? 43. Да, но… как нам узнать, каким будет следующее значение?
Придумайте суждение или формулу, которые (хотя бы с грехом пополам) прогнозируют, каким будет следующее простое число, (в любом заданном ряду чисел), и ваше имя навечно будет связано с одним из величайших достижений человеческого мозга. Вы встанете в один ряд с Ньютоном, Эйнштейном и Гёделем. Разберитесь в поведении простых чисел, и можете потом всю жизнь почивать на лаврах.
Введение
Свойства простых чисел изучались многими великими людьми в истории математики. С первого доказательства бесконечности простых чисел Евклида до формулы произведения Эйлера, связавшей простые числа с дзета-функцией. От формулировки теоремы о простых числах Гаусса и Лежандра до её доказательства, придуманного Адамаром и Валле-Пуссеном. Тем не менее, Бернхард Риман до сих пор считается математиком, сделавшим единственное крупнейшее открытие в теории простых чисел. В его опубликованной в 1859 году статье, состоявшей всего из восьми страниц, были сделаны новые, ранее неизвестные открытия о распределении простых чисел. Эта статья по сей день считается одной из самых важных в теории чисел.
После публикации статья Римана оставалась главным трудом в теории простых чисел и на самом деле стала основной причиной доказательства в 1896 году теоремы о распределении простых чисел. С тех пор было найдено несколько новых доказательств, в том числе элементарные доказательства Сельберга и Эрдёша. Однако до сих пор остаётся загадкой гипотеза Римана о корнях дзета-функции.
Читать полностью »
Почему единицу не относят к простым числам, и когда её вообще начали считать числом
2019-05-07 в 12:19, admin, рубрики: единица, математика, простые числа, теория чисел
Мой друг инженер недавно меня удивил. Он сказал, что не уверен, является число 1 простым или нет. Я удивилась, потому что никто из математиков не считает единицу простым.
Путаница начинается с определения, которое дают простому числу: это положительное целое число, которое делится только на 1 и само на себя. Число 1 делится на 1, и оно делится само на себя. Но деление на себя и на 1 здесь не является двумя различными факторами. Так простое число это или нет? Когда я пишу определение простого числа, то пытаюсь устранить эту двусмысленность: я прямо говорю о необходимости ровно двух различных условий, деление на 1 и само на себя, или что простое число должно быть целым числом больше 1. Но зачем идти на такие меры, чтобы исключить 1?
Читать полностью »
Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
2019-05-05 в 15:06, admin, рубрики: Delphi, Алгоритмы, Занимательные задачки, математика, оптимизация, Программирование, простые числа, решето Эратосфена
Общеизвестно, что Решето Эратосфена (РЭ) один из древнейших алгоритмов, появившийся задолго до изобретения компьютеров. Поэтому можно подумать, что за века этот алгоритм изучен вдоль и поперек и добавить к нему ничего невозможно. Если посмотреть Википедию – там море ссылок на авторитетные источники, в которых запросто утонуть. Поэтому удивился, когда на днях случайно обнаружил, что вариант, который в Википедии преподносится как оптимальный, можно заметно оптимизировать.
Читать полностью »
В распределении простых чисел обнаружена дифракционная картина, примерно как у квазикристаллов
2018-10-22 в 8:19, admin, рубрики: апериодический порядок, Блог компании GlobalSign, визуализация данных, дифракция, квазикристаллы, криптография, математика, мозаика пенроуза, пики Брэгга, простые числа, теория чисел, химия
В марте 2016 года Роберт Дж. Лемке-Оливер и Каннан Соундарараджан из Стэнфордского университета открыли новый шаблон в распределении простых чисел. Оказалось, что простые числа специфически распределяются по числовому пространству. Подробнее см. перевод статьи «Структура и случайность простых чисел» на Хабре.
К изучению темы подключились специалисты из других областей, в том числе химии. И успешно. Профессор теоретической химии Сальваторе Торкуато вместе с теоретиком чисел Мэтью де Курси-Айрлэнд нашли новые шаблоны в распределении простых чисел, о которых раньше не было известно. Оказалось, что распределение простых чисел образует фракталоподобную дифракционную картину, чем-то похожую на картину дифракции у экзотических квазикристаллов.
Читать полностью »
О взаимосвязи простых и иррациональных чисел
2018-10-15 в 14:42, admin, рубрики: rsa, иррациональность, иррациональные числа, математика, простые числа, теория чисел, хаосПосле некоторых моих исследований простых чисел, я обнаружил интересную связь с иррациональными числами. Эта связь дает ответ на вопрос, почему простые числа расположены столь «хаотично» и почему они так сложно устроены. Под катом объяснение этой связи и вариант улучшенного алгоритма RSA. Читать полностью »
Бесконечная алгоритмическая мелодия на основе простых чисел
2018-08-14 в 17:05, admin, рубрики: алгоритм, алгоритмическая композиция, Алгоритмы, бесконечность, математика, музыка, музыкальная пауза, музыкальная теория, музыкальные инструменты, ненормальное программирование, простое число, простые числа, процедурная генерация, узоры, фракталы
Привет! В прошлой статье «бесконечный узор на основе простых чисел» я рассказал про алгоритм, который позволяет генерировать бесконечные красивые узоры, похожие то ли на инопланетные рисунки, то ли на нечто технологическое, подобно устройству микросхем. Однако, алгоритм для генерирования 2D узоров можно так же использовать и для создания мелодий. Подробнее под катом.
Читать полностью »
Бесконечный узор на основе простых чисел
2018-07-22 в 16:08, admin, рубрики: Алгоритмы, бесконечность, математика, ненормальное программирование, Программирование, простые числа, процедурная генерация, процедурная генерация карт, фракталы, фрактальные ландшафты
Привет! Однажды утром мне пришла в голову идея находить "исключающее ИЛИ" между координатами точки пространства и проверять полученное число на простоту. Результат такого простого алгоритма вы можете видеть на картинке. Подробнее под катом.
Читать полностью »
Компрессия больших массивов простых чисел
2018-07-21 в 7:30, admin, рубрики: C, компрессия данных, математика, простые числа, сжатие данных, теория чисел
Свойства простых чисел редко позволяют работать с ними иначе, чем в виде заранее вычисленного массива — и желательно как можно более объемного. Естественный формат хранения в виде целых чисел той или иной разрядности страдает при этом некоторыми недостатками, которые становятся существенными при росте объема данных.
Так, формат 16-разрядных беззнаковых целых при размере такой таблицы около 13 килобайт вмещает всего лишь 6542 простых числа: вслед за числом 65531 идут значения более высокой разрядности. Такая таблица годится разве что в качестве игрушки.
Наиболее ходовой в программировании формат 32-разрядных целых выглядит значительно солиднее — он позволяет хранить около 203 млн простых. Но такая таблица занимает уже около 775 мегабайт.
Еще больше перспектив у 64-разрядного формата. Однако при теоретической мощности порядка 1e+19 значений, таблица имела бы размер 64 экзабайта.