Иллюстрированный самоучитель по Mathematica 5

Факторизация целых чисел с помощью функции FactorInteger. Факторизация чисел Мерсенна.

В ряде задач очень важно знать, насколько быстро можно разложить целое число на простые множители. По этой причине давайте рассмотрим, какие числа функция FactorInteger может разложить на простые множители за приемлемое время. Конечно, мы не собираемся факторизовать все числа подряд (для этого не хватило бы и многотомного труда), а займемся только классическими последовательностями.

Числами Мерсенна, как известно, называются числа М_n = 2ⁿ -1. Как следует из формулы разложения двучлена aⁿ -bⁿ, они могут быть простыми лишь при простом п. При четном n выражение 2ⁿ -1 можно разложить на множители, пользуясь, например, формулой для разности квадратов. Вот первые три числа Мерсенна: М1= 1; M2 == 3; M3 = 7. Дальнейшие вычисления поручим системе Mathematica. Для этого напишем программу для разложения чисел Мерсенна, получающихся при n = 1.2, 3,…, k.

Сначала давайте решим какой-нибудь конкретный пример. Разложим, например, на множители число M₆₇. Марен Мерсенн в 1644 году высказал мнение, что это число простое. Однако ошибочность этого утверждения была установлена Э. Люка только в 1875 году. Давайте же посмотрим, сколько времени потребуется системе Mathematica, чтобы справиться с более трудной задачей – разложением на простые множители. Итак, вводим запрос Factorlnteger[ 2^67-1 ]. и мгновенно получаем ответ.

Вот это да! Mathematica почти мгновенно сделала то, на что математикам потребовалось затратить 231 год!

Теперь можем смело приступить к написанию программы. В качестве последнего числа, разлагаемого на множители, выберем М₂₅₇. Именно это число было исследовано М. Б. Крайчиком, который установил, что оно составное. Программа может выглядеть так:

Однако вывод такой программы выглядит несколько "однолинейно".