Теория чисел и язык Haskell: различия между версиями
Содержимое удалено Содержимое добавлено
Lehych (обсуждение | вклад) м Исправил ссылку на Язык Haskell: О пользе и вреде лени |
|||
Строка 121:
<math>M_n = 2^n - 1</math>
Эта последовательность получила наименование «чисел Мерсенна». Сама по себе она не так интересна, но в ней существуют так называемые простые числа Мерсенна, которые получили свою известность в связи с эффективным критерием простоты Люка — Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые большие известные простые числа. На данный момент самым большим известным простым числом является число Мерсенна <math>M_{30402457} = 2^{30402457} - 1</math>, найденное в декабре 2005 года. Оно содержит <math>9152052</math> десятичных цифры (не актуально, поправить).
Эффективный тест простоты (тест Люка — Лемера) для чисел Мерсенна был предложен в 1878 году и базируется на том наблюдении, что простота числа Мерсенна <math>M_p = 2^p - 1</math> влечёт простоту его индекса <math>p</math>, а также на следующем утверждении: «для простого <math>p</math> число <math>M_p</math> является простым тогда и только тогда, когда оно делит число <math>L_{p - 1}</math>, где числа <math>L_k</math> определяются рекуррентным соотношением — <math>L_1 = 4</math>, <math>L_{k + 1} = L_k^2 - 2</math>».
| |||