Алгебра и пакет Mathematica 5
Факторизация чисел Мерсенна
Числами Мерсенна, как известно, называются числа Мn = 2n-1. Как следует из формулы разложения двучлена
an-bn, они могут быть простыми лишь при простом п. При четном
n выражение 2n-1 можно разложить на множители, пользуясь, например,
формулой для разности квадратов. Вот первые три числа Мерсенна: М1= 1; M2 == 3;
M3 = 7. Дальнейшие вычисления поручим системе Mathematica. Для этого напишем программу для разложения чисел Мерсенна, получающихся при
n = 1,2, 3, ..., k.
Сначала давайте решим какой-нибудь конкретный пример. Разложим, например, на множители число
M67. Марен Мерсенн в 1644 году высказал мнение, что это число простое. Однако ошибочность этого утверждения была установлена Э. Люка только в 1875 году. Давайте же посмотрим, сколько времени потребуется системе Mathematica, чтобы справиться с более трудной задачей — разложением на простые множители. Итак, вводим запрос
Factorlnteger[ 2^67-1 ] . и мгновенно получаем ответ.
{193707721,1}, {761838257287,1}}
Вот это да! Mathematica почти мгновенно сделала то, на что математикам потребовалось затратить 231 год!
Теперь можем смело приступить к написанию программы. В качестве последнего числа, разлагаемого на множители, выберем М257. Именно это число было исследовано М. Б. Крайчиком, который установил, что оно составное. Программа может выглядеть так:
Dо[ Print [n, ": ", Factor-Integer [2^n-1] ],{n,257}]
Однако вывод такой программы выглядит несколько "однолинейно".
1 {}
2 {{3,1}}
3 {{7,1}}
4 {{3,1},{5,1}}
5 {{31,1}}
6 {{3,2},{7,1.}}
7 {{127,1}}
8 {{3,1},{5,1},{17,1}}
9 {{7,1},{73,1}}
10 {{3,1},{11,1},{31,1}}
11 {{23,1},{89,1}}
12 {{3,2},{5,1},{7,1},{13,1}}
13 {{8191,1}}
14 {{3,1},{43,1},{127,1}}
15 {{7,1},{31,1},{151,1}}
16 {{3,1},{5,1},{17,1},{257,1}}
17 {{131071,1}}
18 {{3,3},{7,1},{19,1},{73,1}}
19 {{524287,1}}
20 {{3,1},{5,2},{11,1},(31,1),{41,1}}
Кроме того, он и читается с трудом. Поэтому для преобразования вывода в привычную форму лучше всего использовать макрос, написанный на VBA для Word 2002.
Sub Factorization() i
'Обработка списка множителей
Dim strTemp As String
Dim Msg, Style, Title, Help, Ctxt, Response, MyString, R
Msg = "Хотите продолжить ?" ' Вопрос
Style = vbYesNo + vbCritical + vbDefaultButton2 ' Кнопки
Title = "Разложение на множители"' Заголовок окна
Response = vbYes ' Пока ошибки не обнаружены
Selection.Find.ClearFormatting
'Очистка формата в поле поиска With Selection.Find
.Text = "{" ' Что ищем - открывающую скобку
.Forward = True
.Wrap = wdFindContinue
.Format = False
.MatchCase = False
.MatchWholeWord = False
.MatchWildcards = False
.MatchSoundsLike = False
.MatchAllWordForms = False End With Selection.Find.Execute
'Находим открывающую фигурную скобку списка
strTemp = Selection.Text
If strTemp = "{" Then
' Если нашли скобку, обрабатываем список
Selection.Delete Unit:=wdCharacter, Count:=1
' Удаляем скобку Do '
В цикле обрабатываем все элементы списка
Response = Multiplier '
Обработка множителя и его показателя
If Response = vbYes Then
Selection.MoveRight Unit:=wdCharacter, Count:=1, _
Extend:=wdExtend
strTemp = Selection.Text
' Выбираем очередной символ
If strTemp = "," Then
' Это должна быть запятая
Selection.Delete Unit:=wdCharacter, Count:=l
' Удаляем ее
Selection.Font.Reset ' Сбрасываем форматирование
Selection.InsertSymbol Font:="Symbol",
_ CharacterNumber:=-3916, Unicode:=True
' Знак умножения
End If ' Запятую заменили знаком умножения Else
R = MsgBox("***Ошибка: неправильно записан множитель." _
+ Msg, Style, Title) End If
Loop While strTemp = ","
And (Response = vbYes)
Выполняем цикл, пока не обработаем все
множители 1 или не обнаружим ошибку
•
If strTemp = "}" Then
' Список должен заканчиваться закр. скобкой
Selection.Delete Unit:=wdCharacter, Count:=1
' Удаляем скобку
Else
Response = MsgBox("***0шибка: в конце списка нет } ... " _
+ Msg, Style, Title)
If Response = vbYes Then
' Пользователь выбрал Yes (Да)
MyString = "Yes"
' Запомним, что выбрал пользователь
Else ' Пользователь выбрал No (Нет)
MyString = "No"
' Запомним, что выбрал пользователь
End If End If End If End Sub
Function Multiplier() i
' Обработка множителя (и его степени)
Dim strTemp As String
Dim Msg, Style, Title, Help, Ctxt, Response, MyString
Msg = "Хотите продолжить ?"
' Вопрос к пользователю
Style = vbYesNo + vbCritical + vbDefaultButton2' Кнопки
Title = "Очередной множитель: степень простого"
'Заголовок окна
Response = vbYes ' Пока ошибки не обнаружены
' Selection.MoveRight Unit:=wdCharacter, Count:=l,
Extend:=wdExtend strTemp = Selection.Text
' Выбираем очередной символ If strTemp = "{" Then
' Если открывающая скобка - начало множителя
Selection.Delete Unit:=wdCharacter, Count:=1
' Скобку удаляем Selection.MoveRight Unit:=wdWord,
Count:=l, Extend:=wdExtend Selection.MoveRight
Unit:=wdCharacter,
Count:=1 ' Основание Selection.MoveRight Unit:=wdWord,
Count:=1, Extend:=wdExtend strTemp = Selection.Text
' Основание отделяется , от показателя
If strTemp = "," Then
' Разделитель нашли PowExp
' Обрабатываем показатель
Selection.MoveRight Unit:=wdCharacter, Count:=l, _
Extend:=wdExtend
strTemp = Selection.Text
' Этот символ завершает множитель
If strTemp = "}"
Then ' Это должна быть закрывающая скобка
Selection.Delete Unit:=wdCharacter, Count:=1
' удалить ее Else
' Но ведь в конце же должна быть закрывающая скобка
Response = MsgBox("***0шибка в сомножителе: нет } ... " _
+ Msg, Style, Title)
If Response = vbYes Then
' Пользователь выбрал Yes (Да)
MyString = "Yes" ' Запомним, что выбрал пользователь
Else ' Пользователь выбрал No (Нет)
MyString = "No"
' Запомним, что выбрал пользователь
End If End If Else ' Иначе - а где же запятая?
Response = MsgBox("***0шибка в сомножителе: нет , ... " _
+ Msg, Style, Title) If Response = vbYes Then
' Пользователь выбрал Yes (Да)
MyString = "Yes"
'Запомним, что выбрал пользователь
Else ' Пользователь выбрал No (Нет)
MyString = "No" ' Запомним, что выбрал пользователь
End If End If
Else ' Иначе - а где же открывающая скобка ?
Response = MsgBox("***0шибка в сомножителе: нет { ... " _
+ Msg, Style, Title) If Response = vbYes
Then ' Пользователь выбрал Yes (Да)
MyString = "Yes"' Запомним, что выбрал пользователь
Else ' Пользователь выбрал No (Нет)
MyString = "No" ' Запомним, что выбрал пользователь End If
End If
Multiplier = Response
End Function
Sub PowExpO
i
' Обработка пokaзaтeля
t
Dim strTemp As String
Selection.Delete Unit:=wdCharacter, Count:=1
' Удаляем символ Selection.MoveRight Unit:=wdWord,
Count:=l, Extend:=wdExtend strTemp = Selection.Text
' Это и есть показатель If strTemp = "1"
Then ' Если показатель равен 1
Selection.Delete Unit:=wdCharacter, Count:=1
' Удаляем его
Else ' В противном случае форматируем его как надстрочный
With Selection.Font
.Superscript = True 'Надстрочный
End With Selection.MoveRight
Unit:=wdCharacter, Count:=1
Selection.Font.Reset 'Восстановить стиль
End If End Sub
Этот макрос преобразует разложение
{{3,3}, {5,1}, {7,1}, {13,52},{17,1},{19,551},
{37,1},{73,1},{109,1}, {241,1},{433,1},{38737,1}}
к более привычному виду:
33x5x7xl352xl 7X19S51X37X7 3x109x241x433x38737
Теперь можем воспользоваться созданной программой и составить таблицу разложения чисел Мерсенна на простые множители (табл. Б. 10).
Довольно интересно наблюдать за тем, как Mathematica составляет эту таблицу. Первая сотня чисел Мерсенна разлагается практически мгновенно. Незначительные задержки происходят только на второй сотне. Интересно отметить, что эти задержки в пределах второй сотни происходят и при составных n, т.е. в случаях, когда человек воспользовался бы уже вычисленными ранее разложениями. Это свидетельствует о том, что Mathematica в данном случае не пользуется формулой разности степеней. Впрочем, первая существенная задержка происходит только при значении n = 227 (простое). Однако почти сразу же за ней Mathematica сталкивается с рядом незначительных трудностей, которые она быстро преодолевает, но при n = 251 (простое) происходит вторая существенная задержка. Однако поистине удивительно, что самая существенная задержка происходит, казалось бы, в очень простом случае — при n = 254. Ведь при этом значении и число Мерсенна представляет собой разность квадратов, так что фактически число сразу разлагается на множители, которые только на единицу отличаются от корня квадратного из исходного числа. Так что количество цифр в подлежащих разложению числах фактически на первом же шаге уменьшается вдвое! Кроме того, одно из этих чисел представляет собой число Мерсенна М127, которое уже было разложено на множители ранее (точнее, была установлена его простота). Однако если пропустить это число, то разложения М127 и М256 получаются достаточно быстро.
А вот чтобы на нынешних ПК средней мощности разложить число М. Б. Крайчика (Л/257) прямым применением функции FactorInteger, придется подождать несколько часов.
Давайте теперь обсудим, почему все же для системы Mathematica разложить число Крайчика проще, чем М127. Дело в том, что хотя по формуле разности квадратов M254 = M127х(2127+1), система Mathematica об этом не подозревает, и потому она должна сначала найти множитель M127, а затем доказать его простоту. Кроме того, нужно еще разложить на множители число 2'27+1. Это, правда, чуть легче, поскольку очевидно, что оно делится на 3. Впрочем, необходимость в разложении чисел вида 2"+1 в теории кодирования возникает столь часто, что стоит испробовать возможности системы и в этом случае.
