(И мне кажется, там интересно посмотреть всё интервью; отдельно трогательны рисунки, сделанные рукой самого В.И.А.)
Кстати — такая же картинка есть и в "Мат. понимании природы" В.И.А.,
https://www.mccme.ru/free-books/arnold/VIA-mpp.pdf
https://www.mccme.ru/free-books/arnold/VIA-mpp.pdf
Ну и на этой исторической ноте, кажется, мне правильно на сегодня прекратить дозволенные речи.
Пару недель назад прошёл очередной « Математический праздник » — и подборка задач разных лет (https://olimpiada.ru/article/863 ) мне напомнила о задаче 2001 года С. Маркелова:
olimpiada.ru
«Сорок детей водили хоровод»: любимые задачи организаторов Матпраздника
В этом феврале состоится юбилейный XXX Математический праздник. За прошедшие годы участники этого соревнования решили немало необычных задач. В честь этого события мы попросили математиков, которые участвуют или участвовали в организации праздника, выбрать…
« В книге рекордов Гиннесса написано, что наибольшее известное простое число равно 23021^{377} – 1. Не опечатка ли это? »
Кстати, на самом Матпразднике из этой подборки сделали отдельный стенд, и мне кажется, это была исключительно удачная идея: все подходили и смотрели —
(Да, а вот тут коллеги выложили PDF-файл постера)
Forwarded from Непрерывное математическое образование
mp-wall2.pdf
2.8 MB
обновленный постер с задачами Математического праздника в подходящем для печати качестве
Так вот, сегодняшняя байка посвящена простым числам Мерсенна: простым числам вида M(p):=2^p-1, где p простое.
(Я её уже рассказывал год назад, но в непубличном чате; заранее прошу прощения у тех, кто её от меня уже тогда слышал.)
(Я её уже рассказывал год назад, но в непубличном чате; заранее прошу прощения у тех, кто её от меня уже тогда слышал.)
Чуть больше года назад, в декабре 2018-го, нашли очередное простое число Мерсенна, M(82 589 933), ставшее самым большим известным простым числом — что, разумеется, немедленно пробежало по новостям. А если посмотреть на список самых больших известных простых чисел (https://en.wikipedia.org/wiki/Largest_known_prime_number#The_twenty_largest_known_prime_numbers ), то там из первой десятки только одно не-Мерсенновское, да и остальные визуально очень на них похожи. И с 1952-го года только один раз на три года самое большой известное число было не-Мерсенновским: с 1989 по 1992 « царём горы » было 391581×2^{216193}-1.
При этом Мерсенновских чисел очень мало (это же «почти степень двойки») — при том, что вообще-то простых довольно много: доля простых среди первых n чисел это 1/ln n, что, конечно, стремится к 0 — но довольно медленно. Скажем, из 100-значных чисел простым будет примерно каждое 230-е; собственно, ровно так работает поиск простых для RSA-криптографии: тыкаем в случайные большие числа, пока не наткнёмся на простое. И тысяча-другая попыток тут это много, но не смертельно.(А вот если бы простых от 1 до n было бы порядка sqrt{n}, всё было бы совсем по-другому…)
Так почему же самые большие известные простые — Мерсенновские? Потому что « ищем под фонарём », то есть — потому что именно для них есть очень быстрый алгоритм проверки на простоту, тест Люка-Лемера. И с ним очень интересно разобраться.
Его "замкнутая" формулировка "в готовом к исполнению" виде выглядит, как совершенно непонятный « чёрный ящик »: ясно, куда подключать провода, но как и почему он работает, загадка.
А именно: строим последовательность вычетов s_n по модулю M, где M=2^p-1 — наш кандидат в простые Мерсенна, по следующему рекуррентному правилу:
- начинаем с s_1=4,
- каждое следующее s_{n+1}=s_n^2-2 (mod M).
Теорема. M простое тогда и только тогда, когда S_{p-1}=0.
- начинаем с s_1=4,
- каждое следующее s_{n+1}=s_n^2-2 (mod M).
Теорема. M простое тогда и только тогда, когда S_{p-1}=0.
Пример. Возьмём p=5. По модулю M=31 получаем последовательность
4, 14, 194=8 (31), 62=0 (31) — победа.
Чуть-чуть повторяясь — « Куда заливать бензин и как запускать, понятно. А почему же оно всё работает? »
4, 14, 194=8 (31), 62=0 (31) — победа.
Чуть-чуть повторяясь — « Куда заливать бензин и как запускать, понятно. А почему же оно всё работает? »
Для начала — давайте мысленно поделим последовательность s_n на 2 (благо, что по нечётному модулю M это проблемы не создаёт; ну или можно сначала делить, она останется целой, а потом уже приводить по модулю).
Для новой последовательности t_n реккурентное соотношение это t_{n+1}=2 t_n^2-1.
И это уже начинает что-то напоминать: P(t)=2 t^2-1 это формула для косинуса двойного угла (она же многочлен Чебышева степени 2).
Для новой последовательности t_n реккурентное соотношение это t_{n+1}=2 t_n^2-1.
И это уже начинает что-то напоминать: P(t)=2 t^2-1 это формула для косинуса двойного угла (она же многочлен Чебышева степени 2).
А косинус двойного угла, если перейти в комплексные числа и рассмотреть там z=cos a + i sin a, это просто возведение в квадрат. А череда из k возведений в квадрат это возведение в степень 2^k. И это уже начинает с числами Мерсенна (M=2^p-1) иметь что-то общее — ещё не формально, но на уровне "это явно кусочек от той же головоломки".