Hacker News Digest

Французский математик Эдуард Лукас в XIX веке разработал метод проверки простоты чисел, который используется и спустя 150 лет. Он доказал, что 39-значное число 2¹²⁷ - 1 является простым, применив созданный им тест, который до сих пор остается эффективным для чисел специального вида - простых Мерсенна (чисел вида 2^p - 1, где p - простое). Крупнейшее известное простое число на октябрь 2025 года имеет более 41 миллиона цифр и также является числом Мерсенна.

Тест Лукаса-Лемера работает следующим образом: создается последовательность, где s₀ = 4, а каждый следующий член вычисляется как sₙ = sₙ₋₁² - 2. Число 2^p - 1 будет простым тогда и только тогда, когда (p-2)-й член этой последовательности делится на 2^p - 1 без остатка. Этот метод позволил Лукасу доказать простоту огромного числа без помощи компьютера, что остается рекордом и по сей день.

• Пользователи обсуждают, что такое простое число и как его определить, приводя примеры и алгоритмы, включая классический тест Миллера-Рабина и тест Люка-Лемера.
• Обсуждается, что для малых чисел можно просто проверить делимость на числа до корня из числа, но для больших чисел это непрактично.
• Участники упоминают, что в статье 2002 года AKS о проверке простоты за полиномиальное время было показано, что это возможно, но алгоритм не практичен для использования.
• Также обсуждается, что в Hacker News нельзя просто вставить ссылку на статью за paywall без архивной ссылки, и что читать такие статьи можно в режиме чтения Firefox.
• Участники также обсуждают, что 91 не является простым числом, и что 57 не является простым числом, и что 2^127-1 является простым числом.

Prime Grid
Старт
Строки
Столбцы
« » ·

Для работы страницы требуется включённый JavaScript.

• Пользователи делятся ссылками на визуализаторы простых чисел и обсуждают разные способы отображения: решётки, Ulam spiral, «упаковки» по 100 чисел.
• Отмечают, что при простом числе колонок возникают диагональные полосы из-за одинаковых остатков по модулю.
• Удивляются «густоте» простых даже на больших числах, хотя теорема о простых числах говорит о снижении плотности как 1/log n.
• Просят добавить hover-числа, анимацию, другие основания, 3-D, экспорт изображений.
• Кто-то видит в узорах логотипы, «звёздные врата» или даже «клингонский» текст; другие предупреждают, что часть узоров — псевдопаттерны.

Prime Grid — интерактивная сетка, выводящая простые числа слева-направо и сверху-вниз. Меняй строки и столбцы, ищи визуальные узоры, занимайся «умной» математикой или разгадывай код вселенной.

Уже существует? Не знаем.
Зачем нужно? Тоже не знаем.

Лайфхак: кликни в поле «столбцы», зажми стрелку «вверх» и наблюдай каскадные эффекты.

Дэнни Дуплекс

• Пользователи наблюдают «галактические» вращения и спирали при прокрутке количества колонок, особенно вокруг 400–431.
• Найдены «пустые» диапазоны при 546 колонках: интервалы 243–249 и 297–303 не содержат простых чисел, что объясняется делимостью на множители 546.
• Предложены новые функции: инверсия сетки (показ составных), старт с любого числа, подсветка при клике, фильтрация по простым с заданным арифметическим условием, пропуск чётных и чисел, оканчивающихся на 5.
• Несколько человек сравнили визуализации с Ulam-спиралью, 3Blue1Brown и даже задумались о «порталах» и Game of Life.