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

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

Этот макрос преобразует разложение:

К более привычному виду:

Теперь можем воспользоваться созданной программой и составить таблицу разложения чисел Мерсенна на простые множители (табл. Б. 10).

Довольно интересно наблюдать за тем, как Mathematica составляет эту таблицу. Первая сотня чисел Мерсенна разлагается практически мгновенно. Незначительные задержки происходят только на второй сотне. Интересно отметить, что эти задержки в пределах второй сотни происходят и при составных n, т.е. в случаях, когда человек воспользовался бы уже вычисленными ранее разложениями. Это свидетельствует о том, что Mathematica в данном случае не пользуется формулой разности степеней. Впрочем, первая существенная задержка происходит только при значении n = 227 (простое). Однако почти сразу же за ней Mathematica сталкивается с рядом незначительных трудностей, которые она быстро преодолевает, но при n = 251 (простое) происходит вторая существенная задержка.

Однако поистине удивительно, что самая существенная задержка происходит, казалось бы, в очень простом случае – при n = 254. Ведь при этом значении и число Мерсенна представляет собой разность квадратов, так что фактически число сразу разлагается на множители, которые только на единицу отличаются от корня квадратного из исходного числа. Так что количество цифр в подлежащих разложению числах фактически на первом же шаге уменьшается вдвое! Кроме того, одно из этих чисел представляет собой число Мерсенна М₁₂₇, которое уже было разложено на множители ранее (точнее, была установлена его простота). Однако если пропустить это число, то разложения М₁₂₇ и М₂₅₆ получаются достаточно быстро.

А вот чтобы на нынешних ПК средней мощности разложить число М. Б. Крайчика (Л/257) прямым применением функции FactorInteger, придется подождать несколько часов.

Давайте теперь обсудим, почему все же для системы Mathematica разложить число Крайчика проще, чем М₁₂₇. Дело в том, что хотя по формуле разности квадратов M₂₅₄ = M₁₂₇х(2¹²⁷ +1), система Mathematica об этом не подозревает, и потому она должна сначала найти множитель M_127, а затем доказать его простоту. Кроме того, нужно еще разложить на множители число 2'27+1. Это, правда, чуть легче, поскольку очевидно, что оно делится на 3. Впрочем, необходимость в разложении чисел вида 2"+1 в теории кодирования возникает столь часто, что стоит испробовать возможности системы и в этом случае.