Всем привет! Это мой первый пост на Хабре, потому я представлюсь: меня зовут Костя, я разработчик C++, немного музыкант, начинающий ML инженер и любитель математики. Как не сложно догадаться этот пост будет о моём математическом хобби.
Рубрика «теория чисел» - 2
Новый класс простых чисел, который я открыл случайно
2021-05-03 в 9:22, admin, рубрики: full reptend prime, математика, простые числа, системы счисления, теория чисел, циклические числа, числа фибоначчиЗакономерности в распределении простых чисел
2020-12-26 в 11:02, admin, рубрики: математика, Научно-популярное, проблемы Ландау, простые числа, распределение простых чисел, теория чиселВведение
Простое число — это натуральное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Такие числа представляют огромный интерес. Дело в том, что никто так и не смог полностью понять и описать закономерность по которой простые числа располагаются в ряду натуральных чисел.
Математики открыли новый фронт в битве с древней числовой задачей
2020-09-24 в 10:46, admin, рубрики: математика, Научно-популярное, совершенные числа, теория чисел, эйлерНе одно тысячелетие математиков интересовал вопрос существования нечётных совершенных чисел. В процессе его изучения они составили невероятный список ограничений для этих гипотетических объектов. Но новые идеи на этот счёт могут появиться благодаря изучению иных близких к ним объектов.
Если нечётные совершенные числа и существуют, им придётся удовлетворять абсурдно большому списку ограничений
Будучи ещё старшеклассником, Пэйс Нильсен в середине 90-х столкнулся с математическим вопросом, над которым бьётся и по сей день. Но он не расстраивается: очаровавшая его задача, гипотеза о нечётных совершенных числах, остаётся открытой уже более 2000 лет, что делает её одной из старейших нерешённых задач математики.
Частично таким долгоживущим шармом она обязана простоте формулировки. Число называется совершенным, если это положительное целое, n, сумма делителей которого даёт удвоенное число, 2n. Первый и самый простой пример – это 6, делители которого, 1, 2, 3 и 6, в сумме дают 12, или 2*6. Затем идёт 28, с делителями 1, 2, 4, 7, 14 и 28, дающими в сумме 56. Следующие примеры – 496 и 8128.
Читать полностью »
База данных простых чисел до ста миллиардов на коленке
2020-05-30 в 13:07, admin, рубрики: C#, Алгоритмы, битовый массив, высокая производительность, математика, оптимизация, простые числа, решето Эратосфена, теория чисел, числовые алгоритмы
Самый известный алгоритм для нахождения всех простых чисел, не больших заданного, – решето Эратосфена. Он замечательно работает для чисел до миллиардов, может быть, до десятков миллиардов, если аккуратно написан. Однако каждый, кто любит развлекаться с простыми числами, знает, что их всегда хочется иметь под рукой как можно больше. Как-то раз мне для решения одной задачи на хакерранке понадобилась in-memory база данных простых чисел до ста миллиардов. При максимальной оптимизации по памяти, если в решете Эратосфена представлять нечетные числа битовым массивом, его размер будет около 6 гигабайт, что в память моего ноутбука не влезало. Существует модификация алгоритма, гораздо менее требовательная по памяти (делящая исходный диапазон чисел на несколько кусков и обрабатывающая по одному куску за раз) – сегментированное решето Эратосфена, но она сложнее в реализации, и результат целиком в память все равно не влезет. Ниже предлагаю вашему вниманию алгоритм почти такой же простой, как и решето Эратосфена, но дающий двукратную оптимизацию по памяти (то есть, база данных простых чисел до ста миллиардов будет занимать около 3 гигабайт, что уже должно влезать в память стандартного ноутбука).
Читать полностью »
Вычисление целочисленного квадратного корня
2019-09-30 в 17:16, admin, рубрики: квадратный корень, математика, теория чиселВозникла нужда проверить, является ли целое число квадратом, и если да, то вычислить корень. Причем хочется сделать это в целочисленной арифметике. Понятно, что можно реализовать метод Ньютона в целых числах, но он требует деления на каждом шаге. А нельзя ли по другому? Найти квадратный корень по модулю степени двойки, и проверить, а не будет ли он обычным квадратным корнем.
Читать полностью »
Почему доказательство Великой теоремы Ферма не нуждается в улучшениях
2019-07-26 в 7:00, admin, рубрики: великая теорема ферма, информатика, логика, математика, Научно-популярное, научный метод, теория чиселВ течение десятилетий, прошедших после появления знакового доказательства великой теоремы Ферма, появилось несколько идей по поводу того, как сделать его ещё более надёжным. Однако эти попытки отражают глубокое непонимание того, что делает доказательство важным.
23 июня исполнилось 25 лет с момента взбудоражившего всех объявления от Эндрю Уайлса, в котором он заявил о получении доказательства великой теоремы Ферма – наиболее известной в математике задачи возрастом 350 лет. История, окружающая доказательство Уайлса – семь лет он тайно работал над этим проектом, разрыв в доказательстве, обнаружившийся после июньского объявления, элегантное решение, опубликованное год спустя в совместной работе, написанной Уайлсом вместе с его бывшим студентом Ричардом Тэйлором, получение рыцарского звания в 2000 – вошло в анналы математических легенд.
Читать полностью »
Обобщение задачи Брокара
2019-06-15 в 20:24, admin, рубрики: длинная арифметика, математика, Научно-популярное, проблема брокара, теория чиселИстория
Гильберт в 1900 году на II Международном конгрессе математиков в Париже отметил практическую важность теории чисел. Решение абстрактных задач часто приводило к появлению нового математического аппарата. Ярким примером служит Великая Теорема Ферма, в ходе доказательства которой в конце XX-ого века были исследованы мероморфные функции, применяющиеся современными инженерами-конструкторами на авто- и авиазаводах, а также IT-специалистами в рамках имитационного моделирования. Задачи о "красивых числах" — простых близнецах и совершенных числах, считавшиеся в Древней Греции практически бесполезными, теперь обеспечивают современную криптографию устойчивыми алгоритмами генерации ключей.
В 1913 году Рамануджан популяризирует неопределённое уравнение:
Ранее оно фигурировало в работах Анри Брокара. Как утверждают историки, два математика занялись изучением указанного уравнения независимо друг от друга. Очевидно, факториал растёт быстрее квадрата, поэтому первые решения можно быстро получить перебором значений n. Читать полностью »
Почему единицу не относят к простым числам, и когда её вообще начали считать числом
2019-05-07 в 12:19, admin, рубрики: единица, математика, простые числа, теория чисел
Мой друг инженер недавно меня удивил. Он сказал, что не уверен, является число 1 простым или нет. Я удивилась, потому что никто из математиков не считает единицу простым.
Путаница начинается с определения, которое дают простому числу: это положительное целое число, которое делится только на 1 и само на себя. Число 1 делится на 1, и оно делится само на себя. Но деление на себя и на 1 здесь не является двумя различными факторами. Так простое число это или нет? Когда я пишу определение простого числа, то пытаюсь устранить эту двусмысленность: я прямо говорю о необходимости ровно двух различных условий, деление на 1 и само на себя, или что простое число должно быть целым числом больше 1. Но зачем идти на такие меры, чтобы исключить 1?
Читать полностью »
В распределении простых чисел обнаружена дифракционная картина, примерно как у квазикристаллов
2018-10-22 в 8:19, admin, рубрики: апериодический порядок, Блог компании GlobalSign, визуализация данных, дифракция, квазикристаллы, криптография, математика, мозаика пенроуза, пики Брэгга, простые числа, теория чисел, химия
В марте 2016 года Роберт Дж. Лемке-Оливер и Каннан Соундарараджан из Стэнфордского университета открыли новый шаблон в распределении простых чисел. Оказалось, что простые числа специфически распределяются по числовому пространству. Подробнее см. перевод статьи «Структура и случайность простых чисел» на Хабре.
К изучению темы подключились специалисты из других областей, в том числе химии. И успешно. Профессор теоретической химии Сальваторе Торкуато вместе с теоретиком чисел Мэтью де Курси-Айрлэнд нашли новые шаблоны в распределении простых чисел, о которых раньше не было известно. Оказалось, что распределение простых чисел образует фракталоподобную дифракционную картину, чем-то похожую на картину дифракции у экзотических квазикристаллов.
Читать полностью »
О взаимосвязи простых и иррациональных чисел
2018-10-15 в 14:42, admin, рубрики: rsa, иррациональность, иррациональные числа, математика, простые числа, теория чисел, хаосПосле некоторых моих исследований простых чисел, я обнаружил интересную связь с иррациональными числами. Эта связь дает ответ на вопрос, почему простые числа расположены столь «хаотично» и почему они так сложно устроены. Под катом объяснение этой связи и вариант улучшенного алгоритма RSA. Читать полностью »