Алгебра в программе Mathematica
Что такое система Mathematica
Что такое система MathematicaСистема Mathematica — это полностью интегрированная система компьютерной алгебры. Ее появление в 1988 году оказало очень большое влияние на использование компьютеров в науке и технике. Часто говорят, что именно появление системы Mathematica открыло эру применения компьютерной алгебры в научных и технических вычислениях.
История компьютерных вычислений
История компьютерных вычислений и возникновение компьютерной алгебрыС давних времен человек мечтал о машине, которая могла бы выполнять вычисления. Однако что значит вычислять! Когда компьютеры только появились, они, в основном, были предназначены для численных расчетов. Затем они начали применяться для решения задач управления. И хотя в этих приложениях численные расчеты играют весьма важную роль, всегда были ученые, которые понимали, что результаты вычислений могут интерпретироваться не только как числовые значения физических величин. Еще Лейбниц мечтал построить машину для "вычисления истины".
Впрочем, в самом понятии "научные вычисления" всегда была двусмысленность: прежде чем на сцене появился компьютер, вычисления представляли смесь численного счета с тем, что многие называют "алгебраическими вычислениями", т.е. с операциями над математическими формулами.
Единственным примером чисто численных расчетов является, по-видимому, деятельность неординарных вычислителей, таких как Иноди. Несомненно, что авторы таблиц, в особенности логарифмических, выполняют огромный объем численных расчетов, однако этим расчетам предшествует разработка алгебраических формул и методов, необходимая для того, чтобы работа оказалась в пределах человеческих возможностей.
Жак Иноди
Жак Иноди — один из наиболее известных и самых популярных молниеносных вычислителей. Он родился в 1867 году в очень бедной семье, в Онорато {Пьемонт). Иноди был пастухом, около шести лет от роду его захватила страсть к цифрам. Охраняя свое стадо, он практиковался, работая с числами в голове, и в семь лет мог в уме умножать числа, получая пятизначные результаты. И при этом он не знал таблицу умножения! После смерти матери он оставил родные места и отправился бродяжничать с братом, демонстрируя ручную белку. Брат играл на шарманке, а Жак показывал белку и собирал деньги.
Он говорил со зрителями, которых встречал, об устных вычислениях, в которых они обычно ничего не понимали. На рынке он помогал крестьянам делать их расчеты: "В действительности, — пишет он, — я был сильно удивлен, что эти люди, которые были обычно проницательны, почти ничего не знали о подсчетах, которые я делал почти мгновенно, всего лишь услышав их; это дало мне смелость однажды предоставить аргументы для урегулирования расчета между двумя крестьянами, которые готовы были подраться и которых я успокоил, продемонстрировав, что они оба были не правы; эта перебранка, естественно, собрала толпу, которая была удивлена, что маленький паренек вроде меня лучше знает, как считать, чем два взрослых. Те, кто разбирались в числах, начали задавать мне различные вопросы, на которые я отвечал правильно и очень быстро, все еще оставаясь в недоумении, что кто-то не знает ответов, которые кажутся мне столь естественными. В результате крестьяне начали вызывать меня всякий раз, когда возникали трудности".
Вскоре Иноди начал выступать в кафе, где его представлял коммивояжер М. Домби, который стал его импресарио и повез в турне по провинции, а затем привез в Париж в возрасте 13 лет. Здесь он привлек внимание Камиля Фламмариона, который написал несколько статей о нем в различные научные журналы. Известный антрополог Поль Брока, обследовал его и в своем отчете отметил, что голова Жака Иноди была очень большая и неровная.
В 1892 году, когда ему было 24 года, он вернулся в Париж. К этому времени он уже научился читать и писать и его интеллект заметно развился. По свидетельству Альфреда Бине, он вел себя тихо и скромно, говорил мало и был собран. Его образование было не слишком обширным; и следовательно, число тем для разговоров было ограничено.
Его импресарио М. Торси представил Иноди Академии Наук, которая сформировала комитет по изучению счетчика. В этот комитет входили Дарбу, Пуанкаре, Тиссерант и Шарко; позже в него вошел и Альфред Бине. После многочисленных тестов комитет дал свое заключение. Оно было выражено в отчете Дарбу. По мнению известного математика, фантастические результаты, прежде всего, были обусловлены чудесной памятью. Иноди мог запоминать 400-значные числа. 22-значное число Иноди смог вспомнить через восемь дней, хотя его не предупреждали, что когда-либо попросят об этом. Дарбу отмечает очень важный, хотя и пропущенный большинством проверяющих следующий факт: все методы были изобретены самим вычислителем. Правила, открытые Иноди, отличались от принятых в Европе, хотя некоторые из них имели сходство с применяемыми в Индии.
Альфред Бине предложил Иноди представить число 13411 в виде суммы четырех квадратов. Через три минуты Иноди назвал ему четыре следующих числа:
115, квадрат которого равен 13225; 13, квадрат которого равен 169; 4, квадрат которого равен 16; 1, квадрат которого равен 1. Сумма всех четырех квадратов равна 13411.
Минутой позже счетчик нашел другое решение:
113, которое в квадрате дает 12 769; 25, которое в квадрате дает 625; 4, которое в квадрате дает 16; 1, которое в квадрате дает 1. Сумма четырех квадратов равна 13411.
Наконец, некоторое время спустя (точное время не было записано) Иноди нашел третье решение:
113, которое в квадрате дает 12769; 23, которое в квадрате дает 529; 8, которое в квадрате дает 64; 7, которое в квадрате дает 49. Сумма четырех квадратов равна 13411.
Иноди действительно вычислял с удивительной скоростью. Так, в 1924 году в Обществе Гражданских Инженеров был организован матч между счетчиком и вычислительной машиной (арифмометром) того времени. Иноди победил машину в сложении, вычитании, возведении в степень, извлечении корня и в большинстве умножений. Только в умножении пятизначных чисел машина опередила человека. Кроме того, подобно большинству молниеносных вычислителей, Иноди называл день недели, на который приходится та или иная дата, почти мгновенно, что машина не могла делать.
Психолог Альфред Бине отметил, что память Иноди была сильно специализирована. Хотя Иноди запоминал сотни чисел, он не мог повторить более пяти или шести букв, предъявленных в определенном порядке, например в порядке а, т, g, f, s, m, t, u. Он не мог запомнить две строчки стихов или прозы. С другой стороны, он мог поддерживать разговор и отвечать на вопросы остроумно и по существу, решая в то же время предложенные ему задачи.
Все знаменитые великие вычисления XIX века содержат большое количество манипуляций с формулами. Наиболее известным является, несомненно, расчет Леверье орбиты Нептуна, который был основан на возмущениях орбиты Урана и привел к открытию Нептуна. Наиболее впечатляющие вычисления с карандашом и бумагой выполнены также в области астрономии: Делоне потребовалось 10 лет для вычисления орбиты Луны и еще 10 лет для ее проверки (проверка выявила несколько ошибок в знаках и несколько "потерянных" двоек). Результат не является численным, поскольку он состоит, в основном, из формулы, которая сама по себе занимает 128 страниц 4-й главы его книги. Если бы Делоне мог установить систему Mathematica на Pentium 166, то все вычисления, без учета времени на набор формул, заняли бы около 10 минут!
Однако с появлением компьютеров выполнять численные расчеты стало значительно проще, и благодаря огромным вычислениям иногда удавалось избежать трудоемких алгебраических выкладок. Поэтому для широких кругов инженеров и даже для большинства научных сотрудников именно численные расчеты стали синонимом научных вычислений.
Тем не менее, как уже упоминалось, численные расчеты не позволяют полностью исключить необходимость в алгебраических вычислениях. Ведь написание даже простейших программ требует вывода формул, на которых основан алгоритм. Кроме того, имея удобные формулы, вычисления можно выполнить существенно быстрее, чем без них. И это может играть решающую роль: едва ли кого-нибудь (кроме самих метеорологов) может интересовать 48-часовый прогноз погоды через две недели. Кроме того, во многих численных методах (например, сеточных2) при уменьшении шага объем вычислений возрастает экспоненциально (показателем является обычно размерность сетки).
Поэтому с усложнением решаемых задач роль алгебраических вычислений не только не уменьшилась, но и, наоборот, значительно возросла. Однако часто их приходится выполнять вручную, хотя первые эксперименты по их автоматизации были поставлены еще на машинах первого поколения (в 1953 году). Очень скоро выяснилось, что программное обеспечение алгебраических вычислений должно представлять собой полную систему, включающую метод представления нечисловых данных весьма специальной структуры (формул, уравнений и т.д.), язык, позволяющий манипулировать ими, и библиотеку функций для выполнения необходимых базовых алгебраических операций. Значительно раньше, еще в XIX столетии, Ж. Адамаром была осознана важность так называемых некорректно поставленных задач, для которых оказалось, что арифметика, реализованная традиционным способом, не обладает точностью, достаточной для реализации численных алгоритмов их решения. Поэтому уже в начале 60-х годов прошлого столетия велись интенсивные научные исследования алгоритмов выполнения арифметических операций над числами произвольной длины и произвольного диапазона (так называемая арифметика произвольной разрядности). Уже в середине 60-х годов появились малые ЭВМ, на которых арифметические операции были реализованы не традиционным аппаратным способом, а микропрограммно. В 1965 году в Киеве была создана одна из наиболее уникальных таких ЭВМ — МИР-1. Занимая совсем немного места (стол и тумбочка с пишущей машинкой) и обладая весьма скромной, даже по тем временам, памятью — всего 4 Кбайт, она обладала уникальными возможностями в проведении различных инженерных и научных расчетов. Так как эта машина практически полностью была спроектирована математиками, в ней отсутствовали дорогие технические решения. Зато она обладала входным языком высокого уровня (ассемблер отсутствовал, программа на входном языке высокого уровня интерпретировалась) и возможностью выполнения арифметических операций с произвольной (заданной в начале программы) разрядностью. Конечно, о миллионах цифр не приходилось даже и мечтать, так как программа и все данные должны были уместиться в памяти объемом 4 Кбайт. Чтобы скрыть недостаток финансирования (точнее, его следствие — малый объем памяти), по умолчанию разрядность равнялась 6 (десятичным разрядам). Однако многие задачи решались при разрядности 9, 10, 12, а то и. 18-20 разрядов. Отдельные задачи решались при разрядности 100. Простота входного языка и арифметика произвольной разрядности обеспечили необычно маленькой (по тем временам) и дешевой машине больший успех, чем был у флагмана советской вычислительной техники — БЭСМ-6. Вместе с тем попытки решить новые и все более сложные задачи обнаружили ее основной недостаток — отсутствие возможности выполнять аналитические выкладки. И уже через три года после появления МИР-1, в 1968 году была создана МИР-2, входной язык которой, хотя и являлся расширением входного языка машины МИР-1, имел недвусмысленное название — Аналитик. Это был первый, реализованный в СССР полноценный язык программирования с возможностью выполнять "алгебраические" вычисления. И долгое время, вплоть до появления его очередной версии, он был лучшим.
Успех "алгебраических" вычислений был весьма ощутим, и уже в первой половине 70-х годов прошлого столетия появилось несколько систем компьютерной алгебры; упомяну лишь CLAM (1972 г., машина CDC-6500, 20 000 слов, ориентирована на решение задач общей теории относительности), Reduce-2 (1973 г., машины CDC-6500, 65 000 слов, и IBM-360 (и ЕС-1040), 300 Кбайт, универсальная система), Авто-Аналитик (1973 г., машина БЭСМ-6, 30 000 слов, ориентирована на решение задач математической физики) и Аналитик-74 (машина МИР-3). Если не считать Reduce-2 и Аналитик-74, у которых появились новые версии (знаменитый Reduce-З и Аналитик-79), все они довольно быстро доказали свою практическую непригодность. Ни в одной из упомянутых систем, за исключением Аналитика, например, нельзя было взять интеграл. (Интегрирование само по себе, правда, было предусмотрено в Авто-Аналитике, но фактически интеграл брался только в самых тривиальных случаях.)
Успех (или провал) систем первой половины 70-х годов прошлого столетия обусловил появление новых систем во второй половине этого же десятилетия. Для решения задач квантовой теории поля, в 1977 году в США на ассемблере машины CDC-6500 был реализован специальный язык программирования SCHOONCHIP. Но даже дифференцирование и матричная алгебра в нем предусмотрены не были. Зато в том же 1977 году появилась знаменитая система MACSYMA, на долгие годы ставшая флагманом компьютерной алгебры.
В 80-х годах прошлого столетия вышло большое число новых систем (muMath, CoCoa, AlPi и др.). Тогда же успешно развивалась SCRATCHPAD-2 и активно пополнялись библиотеки Reduce. Одновременно MACSYMA переносилась на новые типы компьютеров и успешно завоевывала сердца и умы все более широких кругов пользователей. Однако уже в 1988 году появилась система Mathematica, почти сразу же (менее чем за год) занявшая ведущие позиции в области применений компьютерной алгебры...
В настоящее время есть множество таких систем, но широко используются, пожалуй, лишь Mathematica, Maple, MuPAD и Derive. Впрочем, в 90-е годы прошлого века широко использовалась также система Axiom, разработанная фирмой IBM. Все упомянутые выше системы, так же как и большинство неупомянутых, являются весьма дружественными по отношению к пользователю. Конечно же, их языки отличаются, количество доступных функций в библиотеках варьируется от нескольких сотен до тысяч, внутренние структуры и даже используемые алгоритмы значительно отличаются друг от друга, но все лидирующие системы имеют много общего.
Разработка, развитие и даже использование этих систем постепенно выделились в автономную научную дисциплину, относящуюся, очевидно, к информатике. Цель данной дисциплины — область искусственного интеллекта, несмотря на то что ее методы все более и более удаляются от этой области. Кроме того, в алгоритмах компьютерной алгебры используются все более тонкие математические средства и совсем недавно доказанные теоремы. Таким образом, этот раздел информатики лежит на стыке нескольких областей, что одновременно обогащает его и делает более трудным в исследовательском плане.
Этот раздел информатики называется "Calcul formel" во французкой литературе и "Computer algebra" — в английской. В русской литературе используются термины "компьютерная алгебра", "символьные и алгебраические вычисления", "аналитические вычисления" и др.
Как начать
Как начатьКаждый человек интуитивно вырабатывает свой стиль работы с системами искуственного интеллекта. Можно, например, рассматривать систему компьютерной алгебры просто как достаточно удобный графический калькулятор (инструмент). Чтобы научиться использовать систему Mathematica таким образом, прочтите соответствующую главу из данной книги. Затем можно рассматривать систему Mathematica как помощника в решении небольших и несложных примеров и задач из учебников. Для этого придется прочитать уже не одну, а несколько глав. Переходя к более сложным задачам, необходимо осваивать теорию их решения и одновременно читать книги вроде этой. Однако, приступая к решению настоящих исследовательских задач, будьте готовы столкнуться с рядом проблем: то компьютер слишком долго считает, то не хватает памяти, то получается формула на 5-10 страниц, а то машина выдает непредвиденный ответ. Можете рассматривать данную книгу как упорядоченный набор примеров, правил, советов и комментариев, которые позволят обойти некоторые ямы и ловушки на этом пути.
Решив воспользоваться системой компьютерной алгебры, вы, возможно, еще раздумываете, какую из них выбрать. Это очень важный вопрос, но ответить на него правильно еще важнее. Вот мой ответ. Хотя почти все современные системы компьютерной алгебры очень и даже очень хороши, выбрать нужно наилучшую. Если все же сомневаетесь, какую, прочтите ее название на обложке данной книги.
Концепция системы Mathematica
Концепция системы MathematicaСпециализированные пакеты для решения численных, алгебраических, графических и других задач появились еще в 60-х годах прошлого столетия. Но система Mathematica отличается от них концептуально: система Mathematica универсальна, так как она предназначена для любых научных и технических вычислений. Для этого в ней предусмотрен язык компьютерной алгебры, который позволяет описать широкий круг объектов, которые могут потребоваться в научных и технических вычислениях, причем в самом языке используется очень малое число первичных объектов.
Кто использует систему Mathematica
Кто использует систему MathematicaОсновная часть пользователей системы Mathematica состоит из профессионалов. Но Mathematica также широко используется в образовании; существует несколько сотен курсов для высшей и средней школы, основанных на ней. С появлением студенческой версии системы, Mathematica стала важным инструментом для студентов по всему миру. Кроме того, она является стандартом для множества организаций и крупнейших университетов мира.
Новое в версии Mathematica 5
Возможно, ранее вы уже использовали какую- нибудь более раннюю версию системы Mathematica, например 2.2, 4.0 или 4.2. Стоит ли удалять старую версию и переходить на новую? На мой взгляд, стоит, потому что версия Mathematica 5 значительно усовершенствована для различных численных и символьных операций на основе алгоритмов нового поколения. Ниже приведен краткий список усовершенствований и, расширений в различных областях.
Численные расчеты
Давайте рассмотрим усовершенствования, внесенные в версию 5 в области численных расчетов.
Символьные расчеты
Существенные усовершенствования были сделаны в версии 5 в части, касающейся символьных расчетов.
Программирование и системное ядро
Существенно усовершенствованы в версии 5 средства программирования и системное ядро.
Интерфейс
В версии 5 значительно улучшен интерфейс.
Стандартные дополнительные пакеты
В программу Mathematica 5, помимо ранее имевшихся приложений, дополнительно включены новые пакеты по статистике (Statistical plots and graphics) и полям алгебраических чисел (Algebraic number fields).
Описание некоторых стандартных пакетов Mathematica
Описание некоторых стандартных пакетов MathematicaНиже описаны важнейшие функции наиболее часто используемых пакетов системы Mathematica.
Алгебра — Algebra
Algebra`Relm`. Этот пакет содержит дополнительные тождества и функции для работы с комплексными числами и функциями.
Анализ — Calculus
Calculus `FourierTransform`. В этом пакете содержится набор функций для численного преобразования Фурье. (Аналитические преобразования Фурье выполняет ядро.)
Calculus`Limit`. Здесь имеется усовершенствованная функция Limit для нахождения пределов выражений, содержащих широкий класс элементарных и специальных функций.
Calculus`VariationalMethods`. Этот пакет содержит набор функций, относящихся к вариационному исчислению (вычисление вариаций и решение уравнений Эйлера-Лагранжа).
Calculus`VectorAnalysis`. В этом пакете содержится обширный набор функций векторного анализа для вычислений в различных трехмерных координатных системах.
Дискретная математика — DiscreteMath
DiscreteMath`Combinatorica`. Этот пакет расширяет систему Mathematica более чем на 450 функций, относящихся к комбинаторике и теории графов. Включает функции построения графов и других комбинаторных объектов, подсчета инвариантов этих объектов и вывода их на экран.
DiscreteMath`Permutations`. Данный пакет предназначен для работы с перестановками. Все функции этого пакета в версии 5 содержатся в пакете DiscreteMath`Combinatorica`.
DiscreteMath`RSolve`. Этот пакет используется при работе с последовательностями, включая разностные уравнения, производящие функции последовательностей и т.д.
Геометрия — Geometry
Geometry`Polytopes`. При использовании этого пакета можно работать с правильными многоугольниками и многогранниками.
Geometry`Rotations`. В этом пакете определены функции для вращения векторов в двух- и трехмерном пространстве.
Графика — Graphics
Graphics`Animation`. В этом пакете представлен набор функций для анимации различными способами: вращение или поворот объекта в двух- или трехмерном пространстве, изменение графика функции при изменении параметра, отображение последовательности графических объектов.
Graphics`Arrow`. Этот пакет вводит графический примитив (линию со стрелкой), который полезен для вывода графиков.
Graphics' Colors'. С помощью этого пакета вводятся дополнительные системы определения цвета; кроме того, здесь содержатся спецификации многих цветов.
Graphics`FilledPlot`. Этот пакет содержит функции для рисования двухмерных графиков с закрашиванием некоторых областей различными цветами.
Graphics`Graphics`. С помощью этого пакета можно рисовать двухмерные графики в различных системах координат с различными шкалами, а также выводить двухмерные диаграммы.
Graphics `Graphics3D`. Этот пакет предназначен для рисования графиков поверхностей, линий и диаграмм со специальными эффектами.
Graphics`ImplicitPlot`. Можно рисовать графики неявных функций, т.е. функций, заданных неявно (как решения уравнений).
Graphics `MultipleListPlot`. Этот пакет содержит функцию для вывода значений нескольких списков на одном графике.
Graphics`PlotField`. Здесь имеются функции рисования двухмерного векторного поля и поля градиента по заданному потенциалу.
Graphics`PlotField3D`. Этот пакет предназначен для рисования трехмерных векторных полей.
Graphics`Polyhedra`. С помощью этого пакета можно нарисовать некоторые известные многогранники.
Graphics`Shape`. Этот пакет позволяет нарисовать некоторые трехмерные объекты, такие как цилиндр, конус, тор, лента Мебиуса и т.д.
Graphics`Spline`. В этом пакете определен графический примитив (сплайн) и связанные с ним функции.
Линейная алгебра — LinearAlgebra
LinearAlgebra`Cholesky`. Этот пакет ранее использовался для вычисления разложения Холесского симметричной положительно определенной матрицы. В версии 5 необходимая функция определена в системе и загрузка пакета не нужна.
LinearAlgebra `MatrixManipulation`. Данный пакет включает функции для разложения матриц (на столбцы, строки и подматрицы) и составления новых матриц из блоков уже имеющихся матриц, а также для других манипуляций с матрицами.
LinearAlgebra`Orthogonalization`. Этот пакет предназначен для нахождения ортонормированного базиса (проектирование, нормализация, метод Грама-Шмидта).
Теория чисел — Number-Theory
NumberTheory`ContinuedFractions`. Это пакет для работы с непрерывными (цепными) дробями.
NumberTheory`NumberTheoryFunctions` В этом пакете определены многочисленные теоретико-числовые функции.
Численные методы — NumericalMath
NumericalMath`BesselZeros`. Этот пакет предназначен для нахождения нулей различных функций Бесселя.
NumericalMath `CauchyPrincipalValue`. В этом пакете содержится функция для подсчета главного значения Коши для интеграла с особенностями.
NumericalMath`Listlntegrate`. Этот пакет позволяет вычислить интеграл таблично заданной функции.
NumericalMath `NLimit`. Здесь содержатся функции для нахождения численными методами производных, сумм, пределов.
NumericalMath`PolynomialFit`. Этот пакет применить метод наименьших квадратов для приближения функции полиномом заданной степени.
NumericalMath`SplineFit`. Данный пакет реализует интерполяцию сплайнами.
Статистика — Statistics
Statistics`Confidencelntervals`. Здесь содержатся функции для расчета доверительных интервалов различных параметров статистического распределения.
Statistics `ContinuousDistributions`. В этом пакете содержатся определения основных непрерывных статистических распределений.
Statistics `DescriptiveStatistics `. Здесь имеются определения характеристик распределений, таких как среднее, дисперсия, мода, медиана и др. Эти характеристики можно вычислять как для данных, заданных списками, так и для различных известных распределений, используя пакеты Statistics `Descriptivestatisti.es `,Statistics`DiscreteDistributions`.
Statistics`DiscreteDistributions`. В этом пакете определены основные дискретные статистические распределения.
Statistics`NormalDistribution`. Здесь определены наиболее часто используемые непрерывные распределения, так или иначе связанные с нормальным (гауссовым) распределением. Все функции данного пакета имеются в пакете Statistics `ContinuousDistributions`, но данный пакет меньше по размеру и загружается быстрее.
Разное — Miscellaneous
Здесь содержится набор столь разнообразных пакетов, что затруднительно даже классифицировать их.
Miscellaneous `Units`. Этот пакет часто используется студентами. Он позволяет преобразовывать единицы измерения различных физических величин.
Отличия систем компьютерной алгебры
Отличия систем компьютерной алгебры от традиционных систем программированияОсвоить входные языки систем компьютерной алгебры гораздо проще, чем входные языки традиционных систем программирования. Действительно, почти во всех системах компьютерной алгебры основным является диалоговый режим, в котором новичок может вводить короткие инструкции и сразу же получать результаты. Сначала требуется знать всего лишь несколько функций, которые позволят представить задачу в виде, очень похожем на ее математическую формулировку. Даже если при переписывании задачи (переформулировке) будут допущены ошибки, в коротких инструкциях в интерактивном режиме их легко обнаружить. А быстрое получение результатов, получение которых с помощью карандаша и бумаги требует десятилетий, а подчас для человека вообще непосильно, воодушевляет пользователя и снимает многие традиционные проблемы, связанные с психологией программирования. И очень часто этого вполне достаточно для решения задачи.
Так что синтаксические тонкости обычно легко осваиваются в процессе работы. Правда, в связи с тем, что с помощью таких систем часто решаются исследовательские задачи, где заранее неизвестен даже приблизительный порядок ответа, иногда приходится разбираться, как представляются и обрабатываются данные.
Среди исследовательских задач часто встречаются такие, в которых очень трудно предсказать время вычисления и размер результатов. В таких задачах очень часто приходится искать более оптимальный метод их решения. Конечно, результаты простых алгебраических вычислений получаются почти моментально, и все идет отлично. Но если это не так, то в исследовательских задачах с увеличением их сложности (с ростом некоторого не всегда очевидного параметра) требуемое время и память возрастают зачастую экспоненциально. Кроме того, оценка временных затрат на вычисления далеко не всегда очевидна. Поэтому при решении исследовательских задач иногда очень важно владеть эффективным стилем программирования и способностью предвидеть объем вычислений.
Системы компьютерной алгебры часто представляют собой примеры систем с искусственным интеллектом. И поэтому их поведение иногда трудно предсказать. Человек далеко не всегда может соперничать с машиной при поиске решения по заданным правилам в достаточно полно определенном массиве данных. Например, уже сейчас далеко не просто предсказать исход шахматной партии между машиной и чемпионом по шахматам. Машина может выиграть и у чемпиона.
Применение системы Mathematica
Применение системы MathematicaХотя первыми пользователями системы Mathematica были инженеры, физики и математики, область ее применения быстро расширилась. Сегодня едва ли можно указать область, в которой программа Mathematica не применяется, ее используют физики, биологи, социологи, инженеры, студенты и школьники, хотя последним пользоваться подсказками этой системы часто запрещается. Программа Mathematica сыграла решающую роль во многих важных научных открытиях и стала стандартным инструментом многих инженеров. Она широко используется в планировании и финансовом анализе, с ее помощью исследовались многие сложные финансовые модели. И, конечно же, система Mathematica стала важным инструментом информатики. Результаты, получаемые с ее помощью, используются также для создания новых, более совершенных версий этой системы.
Расширение системы Mathematica
Расширение системы MathematicaMathematica — это расширяемая система. Кроме внутренних команд ядра системы Mathematica, можно использовать дополнительные команды, которые содержатся в загружаемых пакетах. Некоторые пакеты системы (по алгебре, анализу и т.д.) поставляются вместе с самой программой и являются стандартными. Другие пакеты можно переписать с сервера компании Wolfram Research (www.wolfram.com) или приобрести отдельно.
Чтобы выполнить команду из пакета Mathematica, надо сначала загрузить нужный пакет с помощью команды <
Последняя команда инициализирует все пакеты из папки dir. Вот как, например, можно инициализировать все алгебраические пакеты: <
Развитие системы Mathematica
Развитие системы MathematicaMathematica признана фундаментальным достижением в области компьютерного проектирования. Она является одной из самых больших программ и содержит огромное число алгоритмов и технических новшеств. Среди этих новшеств — независимый от платформы интерактивный документ, называемый блокнотом. Блокноты стали стандартом для многих видов отчета и используются для публикации технических документов.
Mathematica была создана компанией Wolfram Research. Успех системы Mathematica привел к росту компании и появлению большого числа независимых разработчиков, связанных с системой Mathematica. Сегодня существует более сотни специализированных коммерческих пакетов для программы Mathematica, а также несколько периодических изданий и несколько сотен книг, посвященных этой системе.
Хотя многие важные задачи могут
РезюмеХотя многие важные задачи могут быть решены классическими численными методами, для решения большого числа задач необходима арифметика произвольной разрядности. Кроме того, множество задач не может быть решено без применения компьютерной алгебры. Поэтому для решения каких бы то ни было серьезных задач, как правило, требуется система компьютерной алгебры, которая могла бы использоваться в качестве блокнота, калькулятора, помощника и ...языка программирования. Наилучшей среди лучших таких систем является Mathematica.
Алгебра в программе Mathematica
Алгебраические преобразования
Алгебраические преобразованияДавайте посмотрим, как система Mathematica справляется с раскрытием скобок в степенях. Для этого служит функция Expand.
Анализ
АнализХотя систему Mathematica и подобные ей называют системами компьютерной алгебры, обычно в них так или иначе представлены все фундаментальные разделы математики. Возможности системы Mathematica в области математического анализа очень велики, и надо полагать, что Лейбниц, Ньютон и Эйлер были бы счастливы поэкспериментировать в области анализа с таким инструментом. Мы же в этой главе ограничимся простейшими примерами.
Арифметические действия над числами
Арифметические действия над числамиАрифметические действия в системе Mathematica обозначаются как обычно: + (сложение), - (вычитание), * (умножение), / (деление), ^ (возведение в степень).
Впрочем, иногда вместо * достаточно набрать пробел. С делением, правда, есть одна закавыка. Вычислим, например, 10/2.
10/2 5
Получилось! (Здесь и далее опускаются эти надоедливые In [...]:= и Out [...]=.) Но вот вычисление 22/7 даст
22/7 22/7
Результат, конечно, точный, но несколько тавтологичный. Как же получить десятичное приближение? Для этого достаточно сделать хотя бы одно число вещественным, поставив, например, точку после 22 или 7.
22/7. 3.14286
Есть и другой способ: явно применить функцию N, дающую приближенное численное значение аргумента. (Аргументы функций заключаются в квадратные скобки.)
Для этого введите N[22/7] и в результате получится 3.14286
Функция N позволяет с необходимой точностью вычислять некоторые математические константы и использовать их. Например:
N[Pi] 3.14159
Чтобы вычислить число n со 100 значащими цифрами, укажите нужное количество значащих цифр вторым аргументом функции N.
N[Pi,100] 3.14159265358979323846264338327950288419716939937510582097494459230781 6406286208998628034825342117068
Вот как, например, можно решить известную классическую задачу: какое число больше, е? или ?e.
N[Е^Pi-Рi^Е, 10] 0.6815349144
Как видите, е? > ?е. Провести соответствующие вычисления (вместе с оценками точности) вручную не так уж и просто, поэтому обычно первокурсники при решении этой задачи используют свойства функций. Конечно же, в системе Mathematica предусмотрены и функции.
Блокнот и меню
Блокнот и менюЧтобы упростить набор и вычисление выражений, рассмотрим возможности интерфейса (оболочки) системы Mathematica. Чтобы сохранить протокол расчетов (блокнот), из меню Файл (File) выберите пункт Сохранить Как (Save As) и запишите блокнот в файл, например в файл myl (желательно в своем каталоге). Чтобы повторить какое-либо вычисление, достаточно двойным щелчком установить курсор вставки в соответствующую строку и нажать
Дифференцирование
ДифференцированиеДифференцировать в системе Mathematica. не просто, а очень просто! В качестве аргументов команды (функции) дифференцирования D [., . ] нужно указать ту функцию, которую мы намерены продифференцировать, и ту переменную (или переменные), по которой (которым) берется производная. Вот как вычисляется производная функции хn.
D[х^n,х] nx-1+n
А вот так вычисляется частная производная функции sin(xyz) по переменной z.
D[Sin[x у z],z] х у Cos[х у z]
Смешанные частные производные также вычисляются без проблем.
D[Sin[x у z],z,y,x,x] -5 х у2 z2 Cos [х у z] - 4 у z Sin [х у z] + х2 у3 z3 Sin [х у z]
Это же можно записать иначе.
D[Sin[x у z], {x,2},y,z] -5 х у2 z2 Cos [х у z] - 4yzSin[xyz]+x2y3z3Sin[xyz]
Полный дифференциал вычисляется посредством команды Dt:
Dt[Sin[x у z] ] Cosfx у z](у z Dt[x]+x z Dt[y]+x у Dt[z])
где Dt [x], Dt [у] и Dt [z] — дифференциалы переменных х, у и z.
Естественно, что команда Dt применяется и для вычисления полных производных функций многих переменных.
Dt[f[Sin[х у z]],х] Cos[xyz](yz + xzDt[y, x] +xyDt[z, x] ) f [Sin[xyz]]
Здесь Dt [y,x] и Dt [z,x] — полные производные переменных у и г по переменной х. Но следующий результат можно назвать правильным лишь формально.
D[Abs[x],x]/.x->l Abs'[l]
Тут система Mathematica села в калошу. Она знает, что функция [x] — недифференцируемая в точке х = 0, но фактически отказывается вычислять ее производную даже в тех точках, где она дифференцируема. Так спокойнее!?
Функции
ФункцииВ системе Mathematica имеется множество математических функций, их имена вполне естественны, за тем исключением, что имена всех встроенных функций начинаются с прописной буквы. Кроме того, не забывайте, что аргументы функций заключаются в квадратные скобки. Ну, и, конечно же, помните о том, что здесь тригонометрические функции называются так, как к этому привыкли американцы: например, вместо привычного для нас tg (тангенса) в системе Mathematica указывается Tan. Ниже приведены некоторые примеры — выполните сами те из них, которые сочтете интересными.
Ехр[3]-Е^3 0
Ничего неожиданного. Но это не арифметика. Числовые значения здесь не вычислялись. Поэтому сразу получился точный результат. Если бы вычислялись значения, получилось бы нечто совсем иное.
N[Exp[3] ,20]-N[Е^3,20] 0. х10-19
А вот модуль перехода от натуральных логарифмов к десятичным.
N[Log[10,E],100] 0.43429448190325182765112891891660508229439700580366656611445378316586 46492088707747292249493384317483
А ниже вычислены sin 1° и cos 1° (Улугбеку они бы очень пригодились).
N [Sin [Pi/180] ,100] 0.0174524064372835128194-1897851631619247225272030713964268361242764059 738420392807004200192679102134691 N[Cos[Pi/180],100] 0.99984769515639123915701155881391485169274031058318593965832071451153 91811033372153972993952881103455
Как видим, с тригонометрией все в ажуре! Давайте теперь проведем вычисление с корнями, — вычислим приближенное значение числа 2v2, столь излюбленного специалистами по математической логике.
N[2ASqrt[2],100] 2.66514414269022518865029724987313984827421131371465949283597959336492 0446178705954867609180005196417
Конечно, то же самое можно сделать и иначе.
N[2^(2^(1/2) ),100] 2.66514414269022518865029724987313984827421131371465949283597959336492 0446178705954867609180005196417
Можно также ввести переменную и написать так:
х=2^(1/2);N[2^х,100] 2.66514414269022518865029724987313984827421131371465949283597959336492 0446178705954867609180005196417
Говоря о корнях, не могу удержаться, чтобы не показать вам вот это:
(-1)^(1/2) i
Так что этот калькулятор и с комплексными числами справляется без труда! Но прежде чем переходить к алгебре, полезно хотя бы бегло познакомиться с блокнотом и меню системы Mathematica.
Интегрирование
ИнтегрированиеНеопределенные интегралы, или первообразные
Интегрирование в системе Mathematica (как и в жизни) сложнее дифференцирования. Впрочем, формально все просто: неопределенный интеграл вычисляют посредством команды Integrate:
Экстремумы функций
Экстремумы функцийСистема Mathematica позволяет найти экстремумы функций одной и нескольких переменных. Вот как, например, можно найти локальный минимум функции excosx.
FindMinimum[Exp[x]*Cos[x],(х,0}] {-0.0670197,{х>-2.35619}}
А вот как можно найти минимум функции sinxcosy .
FindMinimum[Sin[x]*Cos[у],{х,0},{у,0}] {-1.,{x>-1.5708,y>0.}}
Ну и раз уж речь зашла об экстремумах функций, рассмотрим случай линейных функций.
Линейное программирование
Линейное программированиеИспользуя систему Mathematica, нетрудно решить задачи линейного программирования небольшой размерности. Рассмотрим пример.
Матрицы
МатрицыВ системе Mathematica матрицы представляются в виде списков строк, т.е. в виде списков списков. Вот пример задания матрицы. Матрица задается как список списков.
m1={{1,1,1,1},{а,Ь,с,d},{а^2,b^2,с^2,d^2}} {{1,1,1,1}, {а,b,с,d}, {а2,b2,с2,d2}}
Конечно, привычнее ее видеть как матрицу.
Построение графиков функций двух переменных
Построение графиков функций двух переменныхПостроим, например, график поверхности z — sin(x2 у).
Построение графиков функций одной переменной
Построение графиков функций одной переменнойПостроение графика одной функции, заданной аналитически
Вот как можно построить график функции синус.
Построение графиков
Построение графиковСистема Mathematica богата графическими возможностями. Рассмотрим на примерах построение хотя бы некоторых, наиболее часто встречающихся типов графиков.
Разложение в ряд Тейлора
Разложение в ряд ТейлораВот как система Mathematica разлагает функцию Sin в ряд Тейлора.
Списки и линейная алгебра
Списки и линейная алгебраВ линейной алгебре часто рассматриваются объекты, сконструированные из других объектов. Вектор, например, часто представляется в виде списка чисел (являющихся его координатами в некотором базисе). Матрицы — это прямоугольные таблицы, в каждой клетке которых находится элемент некоторого кольца. Тензоры же являются просто многомерными таблицами. Как же такие составные объекты представляются в системе Mathematica? Оказывается, что для конструирования составных объектов произвольной сложности в системе Mathematica используются списки. Именно их мы и рассмотрим сейчас.
Списки
СпискиСписок — это заключенная в фигурные скобки произвольная последовательность объектов, в которой объекты отделяются друг от друга запятыми. Именно списки используются для конструирования составных объектов. Иными словами, все составные объекты являются списками, причем конструкция объекта отражается в конструкции списка. Самый простой список — линейный. Строка (или столбец) представляется в виде линейного списка. Матрица, являющаяся списком строк (или столбцов), представляется в виде линейного списка линейных списков. Конечно же, с помощью списков можно строить и более сложно устроенные объекты, такие как деревья или различные разновидности графов.
Суммы
СуммыДля вычисления сумм в системе Mathematica имеется команда Sum. Вот как вычисляется, например,
Уравнения
УравненияСистема Mathematica классно решает разнообразные уравнения и их системы.
В системе Mathematica знак равенства (=) в уравнениях представляется посредством
двойного знака равенства (= =). Вот как можно решить уравнение х3 + х - 2 = 0.
Векторы
ВекторыИз всего многообразия составных объектов линейной алгебры проще всего устроены векторы. Поэтому не удивительно, что именно они представляются самым простым видом списков — линейными списками. Фактически вектор представляется как список своих координат. Вот как, например, представляется стандартный базис в R3: e1 = {1, 0, 0}; е2 = {0, 1, 0}; е3 = {0, 0, 1}. А вот так представляется вектор u = {а,b,с} с координатами u = {а,b,с}: u = {а,b,с}. Давайте разложим этот вектор по стандартному базису и посмотрим, что получится.
е1={1,0,0}; е2={0,1,0 };е3={0,0,1),u={a,b, с}; v=a*e1+b*e2+ с*е3 (а,b,с)
Как видите, мы записали разложение вектора u = (а,b,с) по стандартному базису и, выполнив сложение трех векторов (проекций вектора u = {а,b,с) на оси координат), получили вектор v = {a,b,c}. (Как и следовало ожидать, вектор v = u.) Как видим, операции над векторами обозначаются естественным образом. Давайте теперь вычислим скалярное произведение векторов v и u.
u.v а2 + b2 + с2
Естественно, это скалярный квадрат вектора u. Теперь давайте вычислим скалярное произведение вектора u и единичного орта е3.
u.е3 с
Как и следовало ожидать, оно равно соответствующей координате вектора u.
Вычисление пределов
Вычисление пределовСистема Mathematica может вычислять пределы — замечательные и не очень.
Знакомство с системой Mathematica
Знакомство с системой MathematicaПосле того как запустим систему Mathematica 5, получится примерно то что изображено на Рисунок 2.1. Большое белое окно слева- блокнот. Именно в него вводится информация, и именно в нем отображаются результаты. Окно в середине - заставка-приветствие и справка. Окно справа - панель для ввода математических символов греческих букв и т.п. После запуска системы Mathematica в блокнот можно вводить информацию.
Если же по каким-либо причинам активным оказалось другое окно, щелкнув в белом рабочем поле, переключитесь на окно ввода системы Mathematica Введите 2+2 и нажмите комбинацию клавиш
В окне системы вы увидите следующее (Рисунок 2.2).
In[1]:=2+2 Out[l]=4
Алгебра в программе Mathematica
Аргумент комплексного числа функция Arg
Аргумент комплексного числа: функция ArgФункция Arg[z] возвращает аргумент комплексного числа z.
Вот как, например, можно получить аргументы корней четвертой степени из 1.
Целая часть вещественного числа функции Floor и IntegerPart
Целая часть вещественного числа: функции Floor и IntegerPartЕсть множество способов преобразования вещественных чисел в целые. Но важнейшими из них являются округление к целому числу и отбрасывание дробной части.
Округление к ближайшему целому, не превосходящему х: функция Floor[x]
Функция Floor [х] представляет собой наибольшее целое, не превосходящее х.
{Floor[Pi], Floor[-Pi], Floor[0], Floor [2.99], Floor [-2.0001]} {3,-4,0,2,-3}
Именно функция Floor в математике и называется целой частью числа и обычно обозначается через [х]. Заметьте, что эта функция отсекает дробную часть только неотрицательных чисел. Для отрицательных нецелых чисел ее работа иллюстрируется следующим примером.
Floor[-8.12345678] -9
Поэтому если необходимо просто отбросить дробную часть, лучше воспользоваться функцией IntegerPart.
Отбрасывание дробной части: функция IntegerPart
Функция IntegerPart просто отбрасывает дробную часть.
{IntegerPart[2.4],IntegerPart[2.6],IntegerPart[-2.4], IntegerPart[-2.6],IntegerPart[PiA2]}{2,2,-2,-2,9}
"Потолок" вещественного числа — округление к наименьшему целому, не превосходящему х: функция Ceiling
Выражение Ceiling [х] представляет собой наименьшее целое, которое не меньше х.
{Ceiling[Pi],Ceiling[-Pi],Ceiling[0],Ceiling[2.99], Ceiling[-2.0001]} (4,-3,0,3,-2}
Округление вещественного Числа: функция Round
Функции Floor и Ceiling позволяют округлить вещественное число к меньшему или большему целому. Иногда же нужно выполнить округление к ближайшему целому. Именно для этого и предназначена функция Round.
{Round[2.4],Round[2.6],Round[-2.4],Round[-2.6],Round[Р1^2]} {2,3,-2,-3,10}
Однако числа, дробная часть которых равна .5, имеют два ближайших целых. Такие числа функция Round округляет к ближайшему четному целому.
Round[Range[20]-10.5] {-10,-8,-8,-б,-6,-4,-4,-2,-2, 0, 0,2, 2, 4, 4, 6, б, 8, 8,10}
Целая и дробная части вещественного числа
Целая и дробная части вещественного числаВсякое вещественное число представляет собой сумму его целой и дробной частей:
Числитель и знаменатель числа
Числитель и знаменатель числа: функции Numerator и DenominatorФункция Numerator[ехрг] собирает в ехрг все множители с неотрицательными показателями. В качестве ехрг можно использовать целые числа, дроби, комплексные числа и их произведение. То же самое функция Denominator делает для сомножителей с отрицательными показателями. Вот пример.
Число как последовательность (список) цифр
Число как последовательность (список) цифрВ позиционной системе счисления число фактически представляет собой список цифр. Для получения такого списка и работы с ним в системе Mathematica предусмотрено несколько встроенных функций, наиболее важными из которых являются IntegerDigits, DigitCount, RealDigits и FromDigits.
Представление целого числа в виде списка десятичных цифр: функция IntegerDigits
Разговаривая по телефону, иногда приходится передавать какие-нибудь длинные, например двадцатизначные, числа. В этих случаях обычно читают их цифра за цифрой. Число 587999888735555 читают, например, часто так: пять, восемь, семь, девять, девять, девять, восемь, восемь, восемь, семь, три, пять, пять, пять, пять. В программах тоже иногда нужно по числу определить его цифры. Если вы хотите узнать, является ли шестизначное число счастливым, вам придется сравнить сумму первых трех цифр с суммой последних трех. Поэтому не удивительно, что уже в версии 2 системы Mathematica была предусмотрена функция IntegerDigits, которая представляет число в виде списка цифр. Представим, например, число 25! в виде списка цифр.
IntegerDigits[25!] {1,5,5,1,1,2,1,0,0,4,3,3,3,0,9,8,5,9,8,4,0,0,0,0,0,0}
Представление целого числа в виде списка цифр в системе счисления с произвольным основанием: функция IntegerDigits
Но, оказывается, функция IntegerDigits может использоваться также для получения списка цифр в системе счисления, основание которой нужно указать вторым параметром. Основание в таком случае может быть любым натуральным числом, большим единицы. Представим, например, число 60! (я полагаю, оно бы очень понравилось шумерам, если бы они его знали) в их любимой шестидесятеричной системе.
IntegerDigits[60! , 60] {1,20,3,4,48,29,10,11,46,47,21,26,45,46,9,29,47,16,37,50,59, 58,0,33, 59,19,31,10,42,35,8,9,36,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
Иногда нужно представить число в системе счисления не только с заданным основанием, но и с заданным количеством цифр, т.е. дополнить его ведущими нулями в таком количестве, чтобы количество цифр равнялось заданному. Тогда количество цифр в числе нужно задать в качестве третьего параметра функции IntegerDigits.
Вот как число 56 представляется в виде байта.
IntegerDigits[56, 2, 8] {0,0,1,1,1,0,0,0}
А вот как число 25! записывается в 32-разрядных машинах.
IntegerDigits[25! ,2,32] {0,1,1,1,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0}
Представление целого числа в виде списка цифр в нега-двоичной системе счисления
Если снование системы счисления b является отрицательным целым числом, меньшим -1, то такую систему называют нега-позиционной. Например, если b = -2, то такая система называется нега-двоичной, а если b = -4 — нега-четверичной, если b = - 10 — нега-десятичной. Основным преимуществом этих систем является отсутствие знака перед отрицательными числами и, следовательно, отсутствие правил знаков. Дело в том, что всякое число любой из нега-позиционных систем с четным числом цифр отрицательно, а число, отличное от 0, с нечетным числом цифр — положительно. Особый интерес для конструкторов вычислительных машин представляет, конечно, нега-двоичная система. Однако если задать отрицательное основание (-2) в качестве второго параметра, функция IntegerDiglts "заругается".
Что такое число
Что такое числоЧто такое число? Однозначного ответа на этот вопрос нет. Например, комплексное число — это число или все-таки вектор? А действительное число — это число или сечение во множестве рациональных чисел? А если комплексные числа все-таки числа, то кватернионы — тоже числа или уже объекты другой природы? Ну а если даже кватернионы — все-таки числа, то разве не следует к числам причислить и октавы Кэли? Иногда очень удобно считать, что числа — это элементы любого кольца. Но тогда и матрицы (элементы кольца матриц) тоже ведь нужно считать числами! Впрочем, это совсем не глупо, как может показаться на первый взгляд: в кольце матриц размера 2x2, элементами которых являются вещественные числа, можно выделить подкольцо, которое на самом деле является полем, изоморфным полю комплексных чисел. Так что не удивительно, что каждая эпоха в истории математики давала свой ответ на вопрос о том, что такое число.
Не удивительно и то, что в системе Mathematica предусмотрено несколько типов чисел. В качестве базовых типов чисел удобно рассматривать целые, рациональные, вещественные и комплексные числа. Все они могут содержать практически любое количество цифр. (Все же количество цифр, конечно, ограничено объемом имеющейся памяти.)
Чтобы разобраться в этом, давайте рассмотрим классический пример — занимательную задачу из многих популярных книг по математике для младших школьников.
Пример 3.1. Наибольшее число, которое можно записать тремя цифрами. Постановка задачи: какое наибольшее число можно записать с помощью трех цифр?
Ну, конечно, 999, почти не задумываясь, отвечают школьники. И знаете, они по-своему правы. Ведь поскольку в условии задачи говорится о цифрах, то их можно только записывать одна за другой. Поскольку их три, значит, число будет трехзначным. А 999 — наибольшее трехзначное число, причем в его записи используется только три девятки. Но оказывается, что не все так просто. Ведь на самом деле постановка задачи нечеткая. Действительно, в условии ведь не указано, как три цифры можно использовать для записи числа. Ведь каждую из трех цифр можно использовать для записи чисел, а затем над этими числами выполнить какие-нибудь операции. Можно, например, с помощью двух цифр записать число 99, а с помощью оставшейся цифры — число 9, а затем возвести 99 в степень 9: 99".
С вычислением этого числа система Mathematica справляется без малейших затруднений.
999= 913517247483640899
Но можно числа 9 и 99 скомбинировать и иначе: 999. Система Mathematica без труда вычислит и это число.
999= 295126654306527521487534802261977363143592725 17043832886063884637676943433478020332709411004889
Мы сразу видим, что 9" гораздо больше, чем 999. Но вот тут-то оказывается, что есть еще и третий вариант: 99'. Это число имеет 369 693 100 цифр, т.е. более трети миллиарда! Понятно, что во многих компьютерах объем памяти меньше количества цифр этого числа, и потому система Mathematica записать его не сможет. (Если вы все же решили вычислить это число и вам надоело ждать, выберите Ядро<=>Прервать вычисление.)
Впрочем, если допустить еще и операцию вычисления факториала, то, так как 9! = 362880, с помощью трех цифр можно записать еще большее число: 9?? . Это число система Mathematica уж точно записать не сможет! Правда, вычислить показатель степени — число 99!, десятичная запись которого содержит 65 269 цифр, системе Mathematica вполне под силу!
Наконец, замечу, что авторы популярных книжек упустили еще одну возможность: использование скобок. С их помощью (и факториала), даже одной девятки (или любой другой цифры, большей 2), можно выписать бесконечно возрастающую последовательность чисел.
9, 9! = 362880, (9!)!, ((9!)!)!, (((9!)!)!)!, ((((9!)!)!)!)!, ...
Уже число (9!)! содержит 4 282 655 цифр, но система Mathematica справляется и с ним! Но вот предложить ей вычислить следующее число в этой последовательности даже и не пытайтесь!
Разобравшись немного с числами, давайте изучим операции над ними. Как видно из примера, арифметические операции над целыми и рациональными числами, как и во многих других системах компьютерной алгебры, выполняются точно (все цифры результата верные). Вот, например, результат возведения в сотую степень числа пять, найденный системой Mathematica.
5100 = 7888609052210118054117285652827862 29673206435109023004770278930640625
Однако при таком представлении целых или рациональных чисел иногда трудно судить о величине результата. Кроме того, поскольку система Mathematica стремится сохранить точность, она оставляет фактически невычисленными такие выражения, как
Дробная часть вещественного числа функция FractionalPart
Дробная часть вещественного числа: функция FractionalPartПусть х — вещественное число. Тогда его дробную часть {х} можно определить равенством: {х} = х - [х]. По этому, общепринятому в математике определению дробная часть всегда неотрицательна и меньше единицы: 0<{х}<1. Однако в системе Mathematica используется несколько иное определение:
FractionalPart[х] = х - IntegerPart[х].
Поэтому FractionalPart [х] отрицательна для нецелых отрицательных х.
Чтобы освоиться с функцией FractionalPart, напишем программу, которая распечатывает результат применения функции FractionalPart к каждому элементу списка. Прежде всего нам понадобится определить функцию, которая оформляет вывод следующим образом.
FractionalPart[ х ]- результат применения функции FractionalPart к х
Вот как для этого можно определить функцию f.
f=(Print["FractionalPart[",#1,"]=",FractionalPart[#1]] &)
Теперь можем написать программу, в которой функция f применяется к каждому элементу списка.
f/@{x,2.4,0.3999999999999999',2.6,0.6000000000000001\-2.4, -0.3999999999999999",-2.6,Pi,10,-Рi^2,2*Sin[1],Ехр[Pi*Sqrt[163]]}
Вот результат
Экспоненциальное представление
Экспоненциальное представление чисел: функция MantissaExponentФункция MantissaExponent [x] представляет число х в виде списка, который содержит мантиссу и экспоненту числа.
Мнимая часть комплексного числа функция Im
Мнимая часть комплексного числа: функция ImТоже совсем незамысловатая функция, возвращающая мнимую часть комплексного числа.
Im[3 + 4I]4 {Im[a+bI],ComplexExpand[Im[a+b I]]) {Im[a]+Re[b] ,b>
Заметьте, что в случае Im[a+b I] вещественность а и b не предполагается — в отличие от случая, когда используется функция ComplexExpand.
Мнимая единица
Мнимая единицаНа специальной панели символов системы Mathematica имеется мнимая единица, но иногда ее удобно ввести просто как букву I или даже как \ [Imaginaryi] или \ [ImaginaryJ]. Вот примеры.
2I + 1 1+2i 2J+5 5+2i
Модуль (абсолютная величина) числа функция Abs
Модуль (абсолютная величина) числа: функция AbsФункция Abs [ z ] возвращает абсолютную величину (модуль) комплексного числа z. Конечно же, ее аргумент может быть и вещественным.
Отбрасывание малых вещественных чисел функция Chop
Отбрасывание малых вещественных чисел: функция ChopВещественные числа, меньшие 10-10, можно отбросить с помощью функции Chop.
Представление числа непрерывной
Представление числа непрерывной дробью: функция Continued FractionФункция ContinuedFraction [x] преобразует число д: в непрерывную дробь. Количество звеньев определяется точностью числа х. Следующая программа, например, находит представления первых 50 чисел Бернулли в виде цепных дробей.
Do[ Print[2n,":",ContinuedFraction[BernoulliB[2n]]],{n,0,50} ]
Как видно из таблицы, некоторые числа Бернулли представляются цепной дробью с очень небольшим количеством звеньев.
Количество звеньев цепной дроби можно задать явно в качестве второго параметра.
Это позволяет получить наилучшие приближения числа дробями, знаменатели которых не превосходят некоторого числа. Пусть, например, нужно найти первые 20 звеньев цепной дроби, представляющей число
Представление вещественных чисел
Представление вещественных чисел систематическими дробями: функция N. Разрядность и точность вещественных чисел: функции Precision и Accuracy .Оказывается, что если вместо целого числа указать равное ему вещественное (для этого достаточно поставить десятичную точку в записи числа), то в результате также будет записано вещественное число с десятичной точкой.
Преобразование из десятичной системы
Преобразование из десятичной системы счисления в недесятичнуюЧтобы преобразовать число из десятичной системы счисления в недесятичную, нужно вызвать функцию BaseForm, причем в качестве первого ее аргумента нужно указать преобразуемое число, а в качестве второго — основание системы счисления, в которую преобразуется число. В качестве основания системы счисления может быть натуральное число и, такое, что 2
Как видите, если указать основание системы счисления, большее 36, функция "заругается". Так что шумерам и древним вавилонянам крупно не повезло бы, попытайся они записать какое-нибудь число, например 1000000, в своей любимой шестидесятеричной системе счисления. Впрочем, числа, большего 3600, шумеры долгое время не знали. Дело в том, что они не сразу осилили концепцию числа как последовательности цифр, или списка цифр.
Преобразование непрерывной дроби
Преобразование непрерывной дроби в число: функция FromContinuedFractionФункция FromContinuedFraction является обратной к функции Continued-Fraction. Она преобразует цепную дробь в число. Вот пример.
Преобразование в десятичную систему счисления
Преобразование в десятичную систему счисленияХорошо, конечно, что Mathematica, как мы уже видели, действительно умеет многое делать с числами в десятичной системе счисления. Но умеет ли она преобразовывать числа из одной системы счисления в другую? Оказывается, да! Правда, нужно сразу оговориться, что основанием позиционной системы должно быть натуральное число, притом большее 1. Так что никаких комплексных оснований и тем более фибоначчиевых или факториальных систем счисления!
Чтобы ввести число в какой-нибудь системе счисления, сначала нужно указать (в десятичном виде) основание системы счисления n (натуральное число, причем 2<и<36), затем два знака ^^ (крыша), а потом само представление неотрицательного вещественного (или целого) числа без знака в системе счисления с основанием n. Цифры, большие 9, изображаются латинскими буквами от а до z, причем а = 10, b = 11 и т.д., в порядке (латинского) алфавита аж до z = 36. Вот несколько примеров.
{2^^1,2^^10,2^^100,2^^1000,2^^101} {1,2,4,8,5} 16^^ffffaaOO 42949452.80 2^^1001001010110111.11110 37559.9
Только что мы научились преобразовывать числа из недесятичной системы счисления в десятичную. А как же выполнить обратное преобразование, т.е. преобразовать число из десятичной системы в недесятичную?
Приближение вещественных чисел
Приближение вещественных чисел рациональными: функция RationalizeЧто значит найти рациональное приближение вещественного числа? Какое приближение следует считать хорошим? На эти вопросы можно отвечать по-разному.
Mathematica, например, считает, что рациональное число p/q — лежит довольно близко к вещественному х, если существует с, примерно равное 10 -4, такое, что
Разрядность и точность при выполнении операций над числами
Разрядность и точность при выполнении операций над числами.Давайте теперь посмотрим, что происходит с разрядностью и точностью при выполнении действий.
Сопряженное комплексное число функция Conjugate
Сопряженное комплексное число: функция ConjugateВыражение Conjugate [z] представляет собой сопряженное комплексное число z . Вот как, например, можно получить число, сопряженное к х+I у.
Conjugate[х+Iу] Conjugate[x]-IConjugate[у]
Заметьте, что х и у предполагаются комплексными.
Вещественная часть комплексного числа функция Re
Вещественная часть комплексного числа: функция ReЭто совсем незамысловатая функция, возвращающая вещественную часть комплексного числа.
Re[3+4I] 3 Re[a+bI] -Im[b]+Re[a]
Заметьте, что в последнем примере вещественность а и b не предполагается.
Знак числа функция Sign
Знак числа: функция SignЕсли аргумент х — вещественное число, то Sign[x] возвращает —1, 0 или 1, в зависимости от того, является аргумент отрицательным, нулем или положительным. Если комплексное число z отлично от нуля, то Sign[z] по определению равно i/Abs [z]. Рассмотрим пример.
Алгебра в программе Mathematica
Факторизация целых чисел с помощью функции FactorInteger
Факторизация целых чисел с помощью функции FactorIntegerВ ряде задач очень важно знать, насколько быстро можно разложить целое число на простые множители. По этой причине давайте рассмотрим, какие числа функция FactorInteger может разложить на простые множители за приемлемое время. Конечно, мы не собираемся факторизовать все числа подряд (для этого не хватило бы и многотомного труда), а займемся только классическими последовательностями.
Факторизация чисел десятичная
Факторизация чисел, десятичная запись которых состоит из n единицДо сих пор мы изучали быстродействие функции FactorInteger на аргументах, близких к 2n. В двоичной системе счисления запись таких чисел содержит много нулей или единиц подряд. Число Мерсенна Mn, например, записывается п единицами, а число 2n+1 — двумя единицами, между которыми стоит л-1 нуль (рассматриваем случай n > 0). Поэтому может показаться, что функция FactorInteger столь эффективна лишь для чисел, которые имеют специальный вид в двоичной системе счисления. Поэтому давайте изучим возможности этой функции по факторизации больших чисел видов, более случайных с точки зрения теории чисел. Попытаемся разложить, например, числа, десятичная запись которых представляет собой повторение одной и той же цифры л раз. Конечно, если n =1, то эта цифра повторяется только один раз, и вопрос о разложении решается в уме. С другой стороны, даже если n> 1, то, разделив такое число на ту цифру, которая повторяется n раз, получим число, десятичная запись которого состоит из л единиц. Так что для факторизации чисел такого вида достаточно иметь таблицу разложения чисел, десятичная запись которых состоит из n единиц. Обозначим это число через 1n. Как задать такое число? Как легко видеть, число, десятичная запись которого состоит из n девяток, равно 10n-1. Разделив это число на 9, получим число, десятичная запись которого состоит из л единиц: (10n-1)/9. Таким образом, мы убедились, что
(10n-1)/9= 1n= 111............................111 ("единиц).
Заметим сразу, что такие числа могут быть простыми лишь в том случае, если количество единиц n в записи такого числа — простое. Действительно, если n = m k, то такое число делится как на число, состоящее из т единиц, так и на число, состоящее из k единиц. Короче говоря, от m| n => 1m | 1n. (Убедиться в этом очень легко, мысленно выполнив деление "столбиком".)
Теперь несложно написать нужную нам программу.
Do[Print[n,":",FactorInteger[(10^n-1)/9]],{n,70}]
В пределах таблицы простых чисел совсем немного, они получаются лишь при n = 2, 19 и 23. Поэтому при всех четных n число 1 имеет 11 в качестве простого множителя. Несколько сложнее увидеть, что 3k|n=>3k| 1n. (Например, все числа вида 13m делятся на 3, это следует из школьного признака делимости на 3. Аналогично обстоит дело и с числами вида 19m.) Это следует из того, что 3k|1k . Как видим, используя таблицу факторизации чисел вида 1n, составленную с помощью простой программы, совсем несложно подметить простейшие закономерности в разложении данных чисел.
Факторизация чисел Фибоначчи
Факторизация чисел ФибоначчиДавайте теперь рассмотрим несколько иной пример. Попытаемся факторизовать числа такой последовательности, которая не может рассматриваться как некоторое тривиальное изменение последовательности аn с целым основанием а. В качестве такой последовательности можем выбрать, например, последовательность Фибоначчи. Напомним, что последовательность Фибоначчи рекуррентно определяется так:
F1 = F2 = 1, Fn+2 = Fn+1 +Fn.
Если Fn — простое, то либо n = 4, либо n — простое. Теперь построим таблицу факторизации чисел Фибоначчи.
Для этого напишем программу, в которой предусмотрим вывод не только разложения числа Фибоначчи, но и самого числа.
Do[Print[n,":",Fibonacci[n]], ":", FactorInteger[Fibonacci[n]]],{n,270}]
Данная таблица недаром содержит числа Фибоначчи Р„ для п вплоть до 300. Дело в том, что до 1963 года (а это совсем недавно с точки зрения многотысячелетней истории теории чисел) было известно, что числа ФибоначчиFn являются простыми для n = 3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47. Упорные же поиски других простых чисел Фибоначчи в то время никаких результатов не дали. Так что с этой точки зрения наша таблица содержит несколько совсем нетривиальных открытий!
Факторизация чисел Мерсенна
Факторизация чисел МерсеннаЧислами Мерсенна, как известно, называются числа М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 в теории кодирования возникает столь часто, что стоит испробовать возможности системы и в этом случае.
следуя логике изучения чисел, близких
Факторизация чисел вида 10n+1Теперь, следуя логике изучения чисел, близких к 2n, построим таблицу факторизации чисел вида 10n+1. В десятичной системе счисления запись таких чисел начинается и заканчивается единицей, а между этими единицами стоят нули:
10n + 1 = 1000............................00001 (n-1 нулей).
Вспоминая формулы суммы степеней, сразу замечаем, что такие числа могут быть простыми лишь в том случае, если л является степенью двойки, т.е. если n = 2k. (При нечетных и, все такие числа делятся, например, на сумму оснований, т.е. на 11.)
Вот программа, которая строит нужную нам таблицу.
Do[Print[n,":",Factorlnteger[10^n+1]],{n,70}]
простые, можно сказать, почти
Факторизация чисел вида 2n+1Среди чисел вида 2n+ 1 простые, можно сказать, почти не встречаются, ведь число такого вида может быть простым только тогда, когда n является степенью двойки: n = 2*. Такие числа называются числами Ферма:
Fn = 22n +1.
Пьер Ферма утверждал, что все такие числа просты. Однако Л. Эйлер установил, что F5= 232+l делится на 641. Давайте попытаемся составить таблицу разложения чисел вида 2"+1 на простые множители. В свое время (70-е годы прошлого столетия) Дональду Кнуту удалось исхитриться и с помощью тождества 2214+1 = (2107-254-Н) (2|07+254-Н) и мощного (для того времени) компьютера факторизовать это число. Давайте попробуем и мы. Вот необходимая программа.
Do[ Print[n,":",FactorInteger[2^n+1]], {n, 214} ]
Даже на весьма слабеньком компьютере построение нужной нам таблицы занимает всего лишь несколько минут .
Да, результат очень даже впечатляет! Но давайте вспомним, что эта таблица нам понадобилась потому, что (с точки зрения компьютера!) у нас не хватило терпения дождаться разложения числа Мг54 прямым применением функции Factorlnteger. Теперь мы без труда можем написать нужное нам разложение.
М254 = 3x56713727820156410577229101238628035243XMi27.
представляет интерес также факторизация чисел
Факторизация чисел вида 2n-7Наряду с разложениями чисел Мерсенна и чисел вида 2n+1, представляет интерес также факторизация чисел вида 2n7-. Так как эти числа будут натуральными только при n > 2, то в программу нужно вставить начальное значение n, равное 3. Поэтому программа будет иметь следующий вид:
Do[Print[n, ":",Factorlnteger[2^n-7]],{n,3,50}]
Даже на весьма слабеньком компьютере построение нужной нам таблицы занимает всего лишь несколько секунд .
Как видим, при 3<и<50 среди чисел вида 2n-7 простое только одно, соответствующее значению n = 39. Заметные задержки (несколько секунд) при факторизации чисел такого вида возникают лишь при n>200.
Факторизация дробей
Факторизация дробейПрочитав заголовок, вы, возможно, скажете: "Раскладывать дроби на простые множители? Да как же это?! Такой операции в арифметике нет!". Действительно, такой операции вроде бы и нет, но вспомните, как часто приходится раскладывать на простые множители числитель и знаменатель одной и той же дроби. И чтобы вы не мучились, по отдельности вызывая функцию FactorInteger для числителя и знаменателя, можете вызвать ее для всей дроби. Это ведь так удобно! В каком же виде будет представлено разложение? Почти в том же, что и для целых чисел, но только показатели простых множителей знаменателя будут отрицательными. Вот пример:
Factorlnteger[1952/1921]={{2,5},{17,-1},{61,1},{113,-1}}.
Давайте же теперь испытаем функцию FactorInteger в новой роли:
Do[Print[n,":",Factorlnteger[BernoulliB[n]]], {n,2,102,2}]
Результат, как обычно, представим в виде таблицы. Однако оказывается, что разработанный ранее макрос для преобразования разложения в обычную форму уже не годится. Ведь теперь основания (да и сами показатели) степеней могут быть отрицательными. Поэтому в таких случаях основания нужно взять в круглые скобки. Это учтено в новом макросе.
Sub Factorization() 'Обработка списка множителей Dim strTemp As String Dim Msg, Style, Title, Help, Ctxt, Response, MyString Msg = "Хотите продолжить ?" ' Вопрос Style = vbYesNo + vbCritical + vbDefaultButton2 'Кнопки Title = "Разложение на множители" 'Заголовок окна OptPasteSmartCutPaste = Options. PasteSmartCutPaste Options. PasteSmartCutPaste = False Response = vbYes ' Пока ошибки не обнаружены Selection.Find.ClearFormatting ' Очистка формата в поле поиска With Selection.Find .Text = "{" ' Что ищем - открывающую скобку .Forward = True .Wrap = wdFindContinue .Format = False .MatchCase = False .MatchWholeWord = False - . .MatchWildcards = False .MatchSoundsLike = False .MatchAllWordForm? = False End With Selection.Find.Execute ' Находим открывающую фигурную скобку списка strTemp = Selection.Text If strTemp = "{" Then ' Если нашли скобку, обрабатываем список Selection.Delete Unit:=wdCharacter, Count:=1 ' Удаляем скобку Do ' В цикле обрабатываем все элементы списка Response = Multiplier ' Обработка множителя и его показателя Selection.MoveRight Unit:=wdCharacter, Count:=1, _ Extend:=wdExtend strTemp = Selection.Text ' Выбираем очередной символ If strTemp = "," Then ' Это должна быть запятая Selection.Delete Unit:=wdCharacter, Count:=1 ' Удаляем ее Selection.Font.Reset ' Сбрасываем форматирование Selection.InsertSymbol Font:="Symbol", _ CharacterNumber:=-3916, Unicode:=True ' Знак умножения End If ' Запятую заменили знаком умножения Loop While strTemp = "," And (Response = vbYes) ' Выполняем цикл, пока не обработаем все множители ' или не обнаружим ошибку 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 Options.PasteSmartCutPaste" = OptPasteSmartCutPaste End Sub Function Multiplier() i ' Обработка множителя (и его степени) 1 Макрос записан 26.10.2003 Яков Шмидский t Dim strTemp As String Dim Msg, Style, Title, Help, Ctxt, Response, MyString Msg = "Хотите продолжить ?" ' Вопрос к пользователю Style = vbYesNo + vbCritical + vbDefaultButton2 ' Кнопки Title = "Очередной множитель: степень простого" ' Заголовок окна Response = vbYes ' Пока ошибки не обнаружены strTemp = Selection.Text ' Выбираем очередной символ Selection.MoveRight Unit:=wdCharacter, Count:=l, Extend:=wdExtend If strTemp = "{" Then ' Если отрывающая скобка - начало множителя Selection.Delete Unit:=wdCharacter, Count:=1 ' Скобку удаляем Selection.Extend Character:="," ' Расширили выделение до , Selection.MoveLeft Unit:=wdCharacter, Count:=1, Extend:=wdExtend ' Отменили выделение , BaseRepresent Selection.MoveRight Unit:=wdCharacter, Count:=1 ' Основание Selection.MoveRight Unit:=wdCharacter, Count:=l, 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 End If Multiplier = Response End Function Sub PowExp() t ' Обработка показателя t Dim strTemp As String Selection ..Delete Unit :=wdCharacter, Count :=1 ' Удаляем символ Selection.Extend Character:="}" ' Расширили выделение до } Selection.MoveLeft Unit:=wdCharacter, Count:=1, Extend:=wdExtend ' Отменили выделение } strTemp = Selection .'Text ' Это и есть показатель If strTemp = "1" Then ' Если показатель равен 1 Selection.Delete Unit:=wdCharacter, Count:=l ' Удаляем его Else ' В противном случае форматируем его как надстрочный With Selection.Font .Superscript = True 'Надстрочный End With Selection.MoveRight Unit:=wdCharacter, Count:=1 Selection.Font.Reset 'Восстановить стиль End If End Sub Sub BaseRepresent() Dim strTemp As String strTemp = Selection.Text ' Основание If Not MultiplierQ(strTemp) Then ' Selection.MoveLeft Unit:=wdCharacter, Count:=l ' Selection.InsertBefore "(" ' Перед основанием вставим символ { Selection.InsertAfter ")" ' А после него вставим символ ) End If End Sub Function MultiplierQ(strTemp) ret = True If Left(strTemp, 1) = "-" Then ret = False MultiplierQ = ret End Function
Этот макрос преобразует представление
{{-1,n},{2,-1},{-3,-m},{5,-1},{7,-1},{11,-1}, {13,-1},{31,-1}, {61,-1},{2003,1},{5549927,8},{109317926249509865753025015237911,1}}
в такой более привычный вид.
(-1)nх2-1х(-3)-mх5-1х7-1х11-1х13-1х31-1х 61-1x2003x55499278Х109317926249509865753025015237911
Теперь, пользуясь результатами и макросом, можем составить таблицу . Если нужно разложить только, например, числители, можно воспользоваться следующей программой:
Do:[Print[n,":",Factorlnteger[Numerator[BernoulliB[n]]]],{n,2,102,2}].
Так как это разложение играет чрезвычайно важную роль в доказательстве Последней теоремы Ферма, представим его, как обычно, в виде таблицы.
Эта таблица заслуживает внимания. Прежде всего нужно заметить, она может оказать неоценимую помощь при поиске больших иррегулярных чисел. (Напомню, что простое число р называется регулярным, если на него не делится ни один из числителей чисел Бернулли В2, В4, ..., Вp-3. В противном случае простое число называется иррегулярным.) Иррегулярные простые числа долгое время были причиной ужасных неприятностей для всех, кто занимался доказательством Последней теоремы Ферма. Дело в том, что для регулярных чисел эта теорема была доказана Куммером еще в 1850 году. Это было настоящее торжество ферматистов! Наиболее отчаянные предположили даже, что число иррегулярных чисел конечно, и, таким образом, им оставалось якобы рассмотреть лишь конечное число случаев! Нужно заметить, что их предположение не было лишено оснований. Действительно, в пределах первой сотни есть всего лишь три иррегулярных числа: 37, 59 и 67. (В этом легко убедиться, просмотрев составленную нами таблицу.) Однако в 1915 году Иенсен довольно просто доказал, что множество иррегулярных чисел бесконечно. Тогда-то ферматисты занялись изучением иррегулярных чисел вплотную. В 1965 году Эйхлер существенно продвинулся в поисках доказательства Последней теоремы Ферма, а десять лет спустя, в 1975 году, Брюкнер ввел индекс иррегулярности числа р — количество числителей чисел Бернулли В2, В4, ..., В^, делящихся на р, — и тем самым придал результатам Эйхлера вполне обозримую форму. Понятно, что интерес к таблицам, подобным составленной нами (не без помощи системы Mathematica), значительно возрос. Однако даже в 1985 году, после очередного всплеска интереса к Последней теореме Ферма, когда она была доказана для "почти всех" натуральных показателей, таблица, помещенная в одном из лучших университетских учебников по теории чисел — в учебнике 3. И. Боревича и И. Р. Шафаревича, была доведена лишь до п = 60. Так что едва ли будет преувеличением утверждение, что с помощью системы Mathematica мы составили таблицу, о которой несколько поколений ферматистов могли только мечтать!
Кроме того, эта таблица поможет нам понять, как система Mathematica обращается с дробями. Если число дробное (а именно такими и являются числа Бернулли с четными индексами), то знак дроби относится к числителю. В этом легко убедиться, просмотрев нашу таблицу. Действительно, как мы видели из таблицы разложения чисел Бернулли Вn на простые множители, числа B4n-1 отрицательны, а числа B4n-2 положительны. Точно так же распределены и знаки числителей в таблице разложения числителей чисел Бернулли Вn.
Итак, с помощью функции FactorInteger можем разлагать на простые множители не только натуральные и отрицательные числа, но и дроби, — иными словами, все рациональные числа. Таким образом, кажется, мы научились применять эту функцию ко всем числам, к которым применимо понятие разложения на простые множители. Но возможности этой функции шире. Она умеет еще кое-что. "Как? Неужели... Разве это мыслимо, разлагать на множители комплексные числа?", — возможно, подумаете вы. И не ошибетесь!
Факторизация факториалов
Факторизация факториаловФакториалы являются классическим примером больших чисел. В школе, примерно класса с шестого, учителя плавно готовят детей к тому, что факториалы очень быстро растут, а при изучении комбинаторики говорят, что уже 8! = 40320. Тех же, кто этого не устрашится, на школьном кружке пугают тем, что 100! — невообразимо большое число. Такое большое, что даже вычислить его немыслимо. (Но члены школьного математического кружка обычно знают, что это число вычислил Мольтерер еще до появления ЭВМ.) Дня тех же, кто не убоялся этого числа и (зачастую вопреки устрашениям учителей) преодолел конкурсный отбор в вузы, у профессоров есть очередная страшилка: 1000!. Что-то я не видел профессора, который бы выписал десятичную запись этого числа на доске! Наверное, для профессоров оно и вправду страшное! Но не для нас. Мы его (вместе с системой Mathematica) выпишем раньше, чем профессор успеет моргнуть оком.
Факторизация гауссовых чисел
Факторизация гауссовых чиселНапомним, что гауссовыми называются комплексные числа, у которых действительная и мнимая части являются целыми числами. Иными словами, это комплексные числа а+bi, у которых вещественная (а) и мнимая (b) части представляют собой целые числа. Вот примеры гауссовых чисел:
2, 1+2i, i, -i, 1+i, 1-i, 1+7i, 1+555555i, 9999+444i.
На комплексной плоскости гауссовы числа образуют решетку всех точек с целыми координатами. Гауссовы числа называются в честь К. Ф. Гаусса, который обратил на них внимание еще в 1832 году в работе о биквадратичных вычетах. Именно Гаусс понял важность изучения этих чисел и установил их основные свойства.
Как оказалось, множество гауссовых чисел, рассматриваемое с обычными операциями, образует кольцо, являющееся, конечно, подкольцом кольца (даже поля) комплексных чисел. Кольцо целых гауссовых чисел можно рассматривать как расширение кольца целых чисел Z путем присоединения i, поэтому это кольцо обозначается Z[i].
В этом кольце делителями единицы являются лишь +1, -1, i и -i. Так что множество делителей единицы в кольце гауссовых чисел конечно. А потому в этом кольце имеет смысл понятие простого элемента, а, значит, можно выполнять разложение элементов этого кольца на простые множители. Нетрудно доказать, что кольцо целых гауссовых чисел евклидово. Поэтому с точностью до делителей единицы разложение на простые множители в нем единственно. Так что кольцо гауссовых чисел (как и всякое евклидово кольцо) является гауссовым, или факториальным.
Нормой комплексного числа называется квадрат модуля, т.е. квадрат длины отрезка, соединяющего комплексное число с началом координат. Иными словами, это сумма квадратов вещественной и мнимой частей комплексного числа:
N(a+bi) = (а+bi)(а-bi) = a2 +b2.
Нечетное простое число р является простым гауссовым числом тогда и только тогда, когда оно дает в остатке 3 при делении на 4: р = 3 (mod 4). Если же р = 3 (mod 4), то р не является простым в кольце целых гауссовых чисел. Не является простым в кольце целых гауссовых чисел и число 2.
Давайте теперь найдем несколько разложений гауссовых чисел на простые множители.
Factorlnteger[5-51]={(-1,1},{1+i,I},{1+2 i,1},{2+i,1}} FactorInteger[3+1]={{-i,1},(1+i,1},{1+2 1,1)} FactorInteger[-90-180I]={{1+i,2},{1+2 i,2},{2+i,1},{3,2}} Factorlnteger[-182-1261]={{1+i,3},{2 + i,3},{7,1}} FactorInteger[3+I5]={{1+i,1},{4+i,1}} Factorlnteger[777+1111] ={{-1,1},{1+i,1},{1+6 i,l},{2+i,2},{3,l},{6+i,l}} Factorlnteger[153+1 374]={{-i,l},{!+4 i,1},{2+i,1},{4+i,1},{8+7 i,l}} Factorlnteger[7+81]={{7+8i,l}}
Число 7+8 i, как видим, оказалось простым. Заметьте, что Mathematica сама поняла, что разложение нужно выполнять в кольце целых гауссовых чисел. Но как разложить на простые множители в кольце целых гауссовых чисел натуральные числа? Ведь, например, FactorInteger[41] = {{41,1)}.
В подобных случаях, т.е. когда в качестве аргумента функции FactorInteger выступает рациональное вещественное число, а разложить аргумент нужно на простые гауссовы числа, область разложения нужно указать явно. Для этого необходимо с помощью второго аргумента функции FactorInteger установить опцию Gaussianlntegers равной True. Вот несколько примеров, в которых показано, как это делается.
Factorlnteger[41,GaussianIntegers->True]={{-1,1},{4+5i,l},{5+4i,lH FactorInteger[5,GaussianIntegers->True]={{-i,l},{!+2i,i},{2+i,1}} Factorlnteger[2,GaussianIntegers->True]={{-i,1},{1 + i,2}} Factorlnteger[11,GaussianIntegers->True]={{11,1}} FactorInteger[13,GaussianIntegers->True]={{-i,l},{2+3i,l},{3+2 i,l}}
Как видите, ничего сложного!
Факторизация очень больших чисел
Факторизация очень больших чиселКак мы уже видели, функция Factorlnteger вполне справляется с разложением чисел, десятичная запись которых содержит не более 60—70 десятичных знаков (это примерно две сотни двоичных). Хотя именно такие числа чаще всего встречаются на практике, их множество конечно. Дополнение же этого множества до множества натуральных чисел бесконечно! Поэтому иногда приходится раскладывать и числа, содержащие несколько сотен, а то и тысяч десятичных знаков. Конечно, в таких случаях зачастую приходится полагаться на удачу. Однако и здесь может помочь Mathematica. Например, если известно, что некоторое число является большой степенью некоторого основания, то достаточно разложить только основание. Так что этот случай большого числа для процедуры факторизации можно считать тривиальным. Несколько менее тривиальным является случай факториала.
Функция FactorIntegerECM попытка
Функция FactorIntegerECM: попытка факторизации больших чисел МерсеннаДавайте на примере попытки разложения больших чисел Мерсенна рассмотрим, как Mathematica позволяет приблизиться к решению задачи факторизации очень больших чисел.
Факторизация 317-го числа Мерсенна М317
Конечно, можно попытаться применить функцию Factorlnteger. Но это не даст результата (за приемлемое время). Можно, правда, "попросить" функцию Factorlnteger найти хоть какие-нибудь делители числа Мерсенна М317. Для этого нужно воспользоваться опцией FactorComplete->False.
FactorInteger[M317-1,FactorComplete->False]
Результат будет таким.
FactorInteger::facfn: Unable to factor 28072587476617 «64» 65592773657961.
More...
Чуть ниже будут и найденные множители.
{{9511, 1), {280725874766179960361032187226573 45634038278340298769450465 797600439224658035965592773657961,1}}
Хорошо, конечно, что нашли множитель 9511, но вот второй множитель... Неизвестно, даже простой ли он. Можно, конечно, попытаться повторить процедуру для него, но это ни к чему новому не приведет.
Factorlnteger::facfn: Unable to factor 28072587476617 "64" 65592773657961. More... {{2807258747661799603610 321872265734563403827834 0298769450465797600439 224658035965592773657961,1}}
В этом случае все придется сделать вручную:.. Возможно, вы подумали о формулах сокращенного умножения. Да, действительно, часто они помогают. (Мы в этом уже не раз убеждались.) Но в данном случае 317 — простое число (я специально так подобрал индекс числа Мерсенна), и применить формулы сокращенного умножения просто так, "в лоб", не удастся. Придется использовать другую функцию. Она есть в пакете теории чисел, который загружается так: "NumberTheory' FactorlntegerECM'.
Сама функция называется FactorIntegerECM. Ее первоначальный алгоритм придумал X. Ленстра (Н. W. Lenstra) в 1985 году. В нем используется теория эллиптических кривых. Функция FactorIntegerECM очень эффективна там, где FactorInteger не справляется. Правда, с другой стороны, она не столь услужлива, как FactorInteger. Она находит только один множитель, притом не обязательно простой. К тому же она привередлива: ее поведение не предсказуемо, если в качестве аргумента передать ей простое число. Поэтому предварительно нужно проверить, что аргумент не является простым числом. Это делается с помощью функции PrimeQ.
Давайте теперь попытаемся применить функцию FactorIntegerECM для какого-нибудь небольшого числа, например 91. (Это число, как мы знаем, не простое.)
FactorIntegerECM[91 ]
А вот и результат.
13
Да, найден только один множитель... Остальное приходится делать вручную. Рассмотрим теперь более сложный пример.
m=12 n = Prime[10Am] Prime[10Лт+1]
Вот что получилось:
12 899773470806612917304808883
Теперь давайте разложим п (оно составное, так как является произведением двух последовательных достаточно больших простых чисел).
FactorIntegerECM[n]
И вот один из сомножителей: 29996224275851
Вот еще один пример применения функции FactorIntegerECM.
n=(2^58 - 27) * (2^127 - 1) 4903985730770843887365 5151436140637119954221204852703259
Теперь ищем какой-нибудь делитель этого числа.
288230376151711717
Наконец, освоившись с функцией FactorIntegerECM на этих более или менее простых примерах, можем попытаться применить ее к факторизации числа Мерсенна Мт. Как мы помним, оно имеет делитель 9511. Сначала убедимся, что он простой.
PrimeQ[9511] True
Теперь можем разделить на него число Мерсенна М317.
n=(2Л317-1)/9511 28072587476617996036103218722657345 63403827834029876945046579760043922 4658035965592773657961
После этого нужно убедиться, что это число составное.
PrimeQ[n] False
Значит, можно применить функцию FactorIntegerECM.
m=Factor!ntegerECM[n]
Через 205,375 с (процессор Pentium 2,4 ГГц) получаем один из его делителей:
587492521482839879 Он простой.
PrimeQ[m] True
Поэтому можем заниматься только частным n = n/m.
n=n/m
477837358776284792683873587315
9342707436119775645430680034874628800586
6959
Опять нужно проверить, простое ли оно.
PrimeQ[n]
Эта проверка занимает всего лишь 0,016 с, и оказывается, что оно составное.
False
Значит, можем снова применить функцию FactorIntegerECM.
m=Factor!ntegerECM[n]
На этот раз понадобится 727,047 с, чтобы найти очередной делитель. 4868122671322098041565641
Снова нужно проверить, прост ли найденный делитель. PrimeQ[m]
Эта проверка выполняется пoчти мгновенно, и оказывается, что делитель действительно прост.
True
Значит, снова можем заниматься только частным n= n/m.
n=n/m 9815639231755686605031317440031161584572466128599
Опять нужно проверить, простое ли оно.
PrimeQn]
Эта проверка занимает всего лишь 0,015 с, и оказывается, что найденное частное является простым числом.
PrimeQ[ n] True
Таким образом, мы нашли все простые множители 317-го числа Мерсенна М317 и тем самым разложили этого числового великана на простые множители.
М317 = 9511X587492521482839879X486812267 1322098041565641X981563923175568 6605031317440031161584572466128599
Факторизация 337-го числа Мерсенна М337
Чтобы освоить методику применения функций Factorlnteger и FactorIntegerECM, попробуем разложить на простые множители 337-е число Мерсенна M337. Сначала можно попытаться применить функцию Factorlnteger. Но как и в случае 317-го числа Мерсенна M317, это не даст результата за приемлемое время. Тогда применим функцию Factorlnteger с опцией FactorComplete->False, чтобы найти хоть какие-нибудь делители 337-го числа Мерсенна М337.
Factorlnteger[2^337-1,FactorComplete->False]
Результат будет таким.
Factorlnteger::facfn: Unable to factor 57238939242563 "51" 465444456568561. More...
Зато чуть ниже будут найдены делители.
{{18199, 1}, (2806537,1), (95763203297, 1}, {572389392425637497118853974356 80799950268490508661316904465621201465444456568561, 1}}
Иными словами,
М337=18199X2806537X95763203297X572389392425637 497118853974356807999502 68490508661316904465621201465444456568561
Теперь нужно проверить, просты ли найденные делители.
PrimeQ[18199] True PrimeQ[2806537] True PrimeQ[95763203297] True PrimeQ[5723893924256374971188539743568079 99502684905086613169044656212 01465444456565-61] False
Как видите, все они, за исключением последнего (обозначим его временно через n), самого большого, простые. (Все это заняло менее двух секунд.)
Поскольку 337 — простое число (я опять специально подобрал индекс числа Мерсенна), формулы сокращенного умножения "в лоб" применить не удастся. Но ведь мы можем загрузить пакет теории чисел.
<
Теперь, когда пакет загружен, можно вызвать функцию FactorIntegerECM.
FactorIntegerECM[572389392425637497118
85397435680799950268490508661316 90446562120146544445656561]
Мгновенно находится множитель.
726584894969
Давайте проверим, прост ли он.
PrimeQ[726584894969]
True
Оказывается, прост. Поэтому разделим на найденный множитель полученное на предыдущем шаге число, присвоим частное переменной п и проверим, является ли частное простым числом.
n=57238939242563749711885397435680799950268490 508661316904465621201465 44445656561/726584894969 787780473264667429936124208424161983 11394008068822475527239136925369 PrimeQ[n] True
Поскольку полученное частное является простым числом, мы нашли все простые множители 337-го числа Мерсенна М337 и тем самым разложили и этого числового великана на простые множители.
М337=18199x2806537x95763203297x 726584894969x787780473264667429 93612420 842416198311394008068822475527239136925369
Функция FactorIntegerECM: поиск делителей 5011 -го числа Мерсенна М5011
Функция FactorlntegerECM иногда может находить делители таких чисел, которые можно смело отнести к разряду супервеликанов. Еще в середине прошлого столетия было известно, что 5011-е число Мерсенна Мхи — составное. Вот этот супервеликан.
Алгебра в программе Mathematica
Близнецы
БлизнецыИзучая распределение простых чисел, мы узнали, что интервалы, состоящие из составных чисел, могут быть сколь угодно длинными. Однако встречаются и очень короткие интервалы, ограниченные простыми числами. Простые числа 2 и 3 следуют друг за другом, не пропуская между собой ни одного составного числа. Но это, конечно, исключение, больше нигде не встречающееся в натуральном ряду. Но зато немало встречается таких пар простых чисел, между которыми стоит только одно составное число (четное, естественно). Простые числа, разность которых равна 2, называются близнецами. Честно говоря, это наименьшая возможная разность между нечетными простыми числами. (Потому что все простые числа, за исключением 2, нечетны!) Вот как определяется функция, которая отыскивает все пары близнецов среди первых т простых чисел.
TwinPrimes[m_]:= Module[{s=Prime[Range[m]]}, {#,#+2}&/@Extract[s,Position[Dropfs,1]- Drop[s,-l],2]]]
Вот, например, список пар близнецов среди первой тысячи простых чисел.
Число простых чисел не превосходящих х (функция PrimePi[x])
Число простых чисел, не превосходящих х (функция PrimePi[x])Согласитесь, изучив все тонкости искусства составления таблиц простых чисел, было бы нелогично пренебречь искусством составления таблиц на основе уже созданных. Почему бы, имея полную (значит, бесконечную!) таблицу простых чисел, не поинтересоваться, сколько чисел в этой таблице не превосходят данного числа х. Иными словами, определить число простых чисел, не превосходящих х. Это число в учебниках теории чисел обозначается л(х). Функция п(х) привлекала внимание уже античных математиков. Евклид, например, установил, что она неограниченно возрастает с ростом аргумента. Изучением этой функции занимались почти все великие математики Прошлого, ее исследовали Лежандр, Чебышев, Риман, Адамар, Валле-Пуссен, Чудаков, Виноградов, Коробов, Литлвуд, Сельберг, Эрдеш, Ингам, Прахар, Пан Чен-тонг, Чен-ин-рун, Титчмарш, Мейссель, Рогель, Чипола, Мертенс, Гаусс, Бертран, Вейль, Линник, Бомбьери...
В системе Mathematica эта функция называется PrimePi. Система Mathematica может вычислить ее значения практически в мгновение ока... Правда, не все.
Доказательство (или опровержение) простоты заданного числа
Доказательство (или опровержение) простоты заданного числаИногда нужно не только знать, простое или составное данное число, но и иметь доказательство (или опровержение) его простоты. Конечно, система Mathematica не пишет развернутый текст такого доказательства (или опровержения), но она может выдать систему чисел, доказывающую (или опровергающую) простоту заданного числа. Такая система чисел называется свидетельством, или сертификатом. Что может быть сертификатом? В принципе это зависит от "внутренней кухни" той системы, которая генерирует сертификат. В случае составного числа можно указать, например, его нетривиальный делитель. При составном числе n можно также указать такое а, для которого не выполняется сравнение an-1 =1(modn). Система Mathematica для установления простоты числа использует теорию эллиптических кривых. Основанный на ней алгоритм, придуманный Аткином (Atkin), Голдвассером (Goldwasser) и Кильяном (Kilian), является в настоящее время наилучшим, если не принимать во внимание квантовых компьютеров, пока еще не реализованных. Этот алгоритм подробно описан в статье Atkin А. О. L. and Morain F. Elliptic Curves and Primality Proving (Mathematics of Computation, 1993, pp. 29-68). Однако он довольно сложен, и в настоящее время даже не все студенты-математики изучают его (как и теорию эллиптических кривых). Поэтому пользуются им чаще всего профессионалы. Тем не менее в отдельных случаях такой сертификат вполне понятен и для школьника. Вот пример. Вызвав функцию PrimeQCertificate[3837523], получим сертификат {2, 3837522, 3837523}, который показывает, что 238"522(mod3837523) не равно 1. (Сертификаты, опровергающие простоту, легко распознать: они всегда состоят из трех чисел.)
Функции PreviousPrime и NextPrime и случайные простые числа
Функции PreviousPrime и NextPrime и случайные простые числаВ пакете теории чисел (загружается по команде <
Функция PrimeQ
Функция PrimeQЗдесь я хотел бы сказать несколько слов о том, как трудно решить, является ли заданное число простым.
Вальтер Боро. Дружественные числа. Открытая лекция, пропитанная при вступлении в должность в Боннском университете
Пожалуй, здесь не будет лишним отметить ошибочность довольно распространенного мнения, будто данная тема — занятие, подходящее лишь для тупых вычислителей, а для настоящих математиков слишком скучное.
Вальтер Боро. Дружественные числа. Открытая лекция, прочитанная при вступлении в должность в Боннском университете
В предыдущей главе, разлагая числа на простые множители, нам уже приходилось проверять числа на простоту. Как вы помните, для этого служит функция PrimeQ, название которой заканчивается прописной буквой Q (question — вопрос), что означает, что она в качестве значения выдает True или False. Числа, ассоциированные с 1 (например, 1 и -1), она к простым не относит.
PrimeQ[1] False PrimeQ[-1] False
Кроме того, как и следует ожидать, она применима и к целым отрицательным числам, причем PrimeQ[-n] = PrimeQ[n]. Более того, она применима к целым гауссовым числам, и если ее аргумент — число с ненулевой мнимой частью, она осуществляет проверку на простоту именно в области гауссовых чисел. Однако если вы хотите в кольце гауссовых чисел проверить на простоту число с нулевой мнимой частью, придется указать опцию GaussianIntegers->True.
PrimeQ[5] True PrimeQ[5+0 I] True PrimeQ[5,Gaussianlntegers-XTrue] False
Пример 5.1. Составим таблицу нескольких первых чисел Ферма с указанием их простоты. Вот что надо ввести в блокнот.
Функция Prime[n] — nе простое число рn
Функция Prime[n] — n-е простое число рnВ предыдущей главе, разлагая числа на простые множители, мы опустили вопрос о том, как составляются таблицы простых чисел. Тем не менее этот вопрос интересовал еще древних греков, и Эратосфен изобрел решето, пользоваться которым умеет каждый пятиклассник. Однако обычно незачем заниматься столь утомительным занятием: в необходимых случаях система Mathematica изготовляет это самое решето и трясет его сколько надо. Пользователю же предоставляется функция Prime [n], которая возвращает n-е простое число рn. Поэтому, чтобы построить таблицу первых 100 простых чисел, достаточно одной команды.
Количество простых чисел на открытом слева отрезке (а b]
Количество простых чисел на открытом слева отрезке (а, b]С помощью функции PrimePi несложно подсчитать и количество простых чисел на открытом слева отрезке (а, b]. Помните только, что если вы пользуетесь выражением k(b)-n(а), т.е. выражением PrimePi [b] -PrimePi [a], то в случае простоты простое число b будет посчитано, а простое число а — нет. Иными словами, подсчет осуществляется на открытом слева отрезке (а, b]. А что, если нужно посчитать простые числа на замкнутом с обоих концов отрезке [а, b}1 Ничего сложного: в качестве аргумента можно взять не а, а несколько меньшее число, ведь аргументом функции PrimePi может быть любое вещественное положительное число. Давайте посчитаем, например, количество простых чисел в 1-й, 2-й, ... , 20-й сотне миллионов натуральных чисел. Вот как это можно сделать.
delta=100000000; PrimePiAB[delta_Integer?Positive,xk_Integer?Positive]:= Block[{k=0, x=delta, kt=0 }, While[x<=xk, {kt=PrimePi[x]; Print[x,":",kt,":",kt-k]; k=kt; x=x+delta}]] PrimePiAB[delta,10 delta]
Полученные результаты удобно представить в виде таблицы .
В приведенной выше программе мы воспользовались тем, что интервалы примыкают друг к другу. Однако так бывает не всегда. Иногда нужно подсчитать количество простых чисел в интервалах заданной длины, причем начала интервалов расположены на числовой оси так, что конец очередного интервала не совпадает с началом следующего. Подсчитаем, например, количество простых чисел в интервалах длиной 150000, причем пусть начинаются эти интервалы в точках х= 106, 107, ... , 1014. Для этого случая пригодится следующая функция.
DeltaPi[x_,delta_]:= Block[{xk=x+delta,k=PrimePi[xk]}, Print[x,"-",xk,":",k-PrimePi[x]]]
С помощью этой функции нетрудно написать и нужную нам программу.
delta=150000;
Do[DeltaPi[10^n,delta],{n,6,14)]
Результаты отформатированы в виде таблицы.
Множество простых чисел Primes и предикат х € Primes
Множество простых чисел Primes и предикат х € PrimesВ системе Mathematica имеется также множество (область) простых чисел Primes. Его также можно использовать для проверки простоты числа. Нужно просто проверить, принадлежит ли число этому множеству. Убедимся, например, что число 1234567 составное.
1234567€Primes False
Наибольшее простое число меньшее n — PreviousPrime[n]
Наибольшее простое число, меньшее n, — PreviousPrime[n]Функция PreviousPrime [n] генерирует наибольшее простое число, меньшее n. Если n не больше 2, будет сгенерировано отрицательное простое число.
PreviousPrime[1] -2 PreviousPrime[2 ] -2 PreviousPrime[-72] -73 PreviousPrime[1ООО] 997
Функция PreviousPrime [n] работает относительно быстро даже для большого аргумента.
Наименьшее простое число большее n — NextPrime[n]
Наименьшее простое число, большее n, — NextPrime[n]Функция NextPrime[n] генерирует наименьшее простое число, большее n.
NextPrime[-1000] -997 NextPrime[-l] 2 NextPrimeflOOO] 1009 NextPrime[1009] 1013
Функция NextPrime[n] работает относительно быстро даже для большого аргумента.
Пифагоровы треугольники у которых
Пифагоровы треугольники, у которых длины двух сторон выражаются простыми числамиКак известно, треугольники, у которых длины двух сторон выражаются целыми числами, называются пифагоровыми. Хорошо известно, что длина ни одной из сторон пифагорового треугольника не может быть равна 2. Поэтому у пифагоровых треугольников длины сторон могут выражаться только нечетными простыми числами. А потому длина хотя бы одной из сторон пифагорова треугольника должна быть четной (по теореме Пифагора) и потому выражается составным числом. (Составным потому, что четным, отличным от 2.) Боле того, несложно доказать, что если р и q — длины сторон пифагорова треугольника, выражающиеся простыми числами, то р2 = 2q -1.
И наоборот, если существуют такие простые числа р и q, что р2 = 2q - 1, то в прямоугольном треугольнике с гипотенузой q и катетом р второй катет равен vq2 - р2 = q -1 ,
и потому такой треугольник будет пифагоровым. Для нахождения пифагоровых треугольников, у которых длины двух сторон выражаются простыми числами, можно применить функции PrimeQ и NextPrime. Область поиска ограничим теми треугольниками, у которых меньший катет р не превосходит заданного числа п. Достаточно найти длину меньшего катета р и длину гипотенузы q, поскольку длина второго катета на единицу меньше длины гипотенузы: q-1
Поиск отрезков натурального ряда
Поиск отрезков натурального ряда, состоящих только из составных чиселЗа одним-единственным исключением pn =2, р2 = 3, числа рn и рn+1 не являются смежными в натуральном ряду. Еще Евклид знал, что существуют сколь угодно длинные отрезки натурального ряда, целиком состоящие из составных чисел. Как же найти отрезок натурального ряда, целиком состоящий из составных чисел? Для этого полезно определить следующую функцию.
Простые числа близкие к числам определенного вида
Простые числа, близкие к числам определенного видаВ ряде областей науки и техники, например в теории кодирования, важно знать простые числа, близкие к числам определенного вида (чаще всего к степеням таких оснований, как 2, 3 и 10). Вне сомнения, их можно было бы найти в обычных таблицах простых чисел. Однако таблицы нужного размера не могли бы поместиться даже в многотомных изданиях. Поэтому существуют специальные таблицы, в которых приводятся только простые числа, близкие, например, к 2n, 3n и 10n.
Но составить такие таблицы для достаточно больших n довольно трудно, и, несмотря на компактность, такие таблицы зачастую весьма неполны. С помощью системы Mathematica несложно составить такие таблицы самостоятельно. Допустим, таблица должна содержать десять наибольших простых чисел, предшествующих N, и десять простых чисел, следующих за N. Можно ограничиться случаем достаточно больших N, например N>1000, поскольку при меньших N вопрос решается с помощью таблиц простых чисел, помещаемых обычно в учебниках для пятиклассников.
Давайте попытаемся составить нужную нам программу, например, для степеней 10. Чтобы результаты выглядели наглядно, нужно предусмотреть их преобразование в таблицу с помощью текстового процессора, например, Word. Поэтому необходимо предусмотреть такой формат результатов, который было бы легко отформатировать (преобразовать в таблицу). Для этого можно предусмотреть двоеточие : в качества разделителя колонок и два двоеточия : : в качестве разделителя строк таблицы. Вот как может выглядеть программа.
Случайное простое число в заданном
Случайное простое число в заданном интервале — Random[Prime, {n, m}]Иногда нужно сгенерировать какое-нибудь случайное простое число, лежащее в заданном интервале. Для этого используется конструкция Random [Prime, {n, m}]. Вот несколько примеров ее использования.
Random[Prime,{10^6,10^12}] 837590772197 Random[Prime,{10^6+0.5,10^12}] 924457361921
Конечно, если в указанном интервале простых чисел нет, будет сгенерировано предупреждение. Вот пример некорректного вызова.
Таблицы простых чисел
Таблицы простых чиселСтудент на экзамене: Чтобы составить таблицу простых чисел, нужно трясти решето. Преподаватель: Сколько раз? Студент: Ну, пока не вытрясется все лишнее.
Мехматовский фольклор
Тест на простоту
Тест на простотуЧтобы сказать, является ли простым заданное число из 15 или 20 цифр, не хватит всей жизни, даже если использовать все, что уже известно.
Мерсенн, XVII в.
Что задача различать простые и составные числа, а последние разлагать на простые множители, принадлежит к важнейшим и полезнейшим задачам во всей арифметике и что она занимала ум как древних, так и современных математиков, настолько известно, что было бы излишним тратить на это много слов. Тем не менее следует признать, что все до сих пор предложенные методы или ограничиваются частными случаями, или настолько громоздки и трудоемки, что ... в основном едва ли могут быть применимы ... к большим числам ...; достоинство науки требует, чтобы прилежно усовершенствовались все вспомогательные средства, могущие помочь в решении этой знаменитой проблемы.
К. Ф. Гаусс. "Disquisitiones Arithmeticae" ("Арифметические исследования ")
Алгебра в программе Mathematica
Линейное представление наибольшего
Линейное представление наибольшего общего делителя — функция ExtendedGCDВ ряде задач необходимо найти не только наибольший общий делитель нескольких чисел, но и его представление в виде линейной комбинации этих чисел. Именно эту задачу решает функция ExtendedGCD. Функция ExtendedGCD [ n1, n2, ...] возвращает список {g, { r1 , r2, ...}}, такой, что g= GCD [n1, n2, ...] и g = r1n1+r2n2 + .... Вот примеры.
{g,{r,s}}=ExtendedGCD[n=45,m=36] (9,{!,-!}}{g,{r,s}}=ExtendedGCD[210°+3,З50 + 8] {1,{62013782892351778750374,-109502757290992473821761130785} }
Пример 6.7. Единица как линейная комбинация чисел Ферма. Так как числа Ферма являются взаимно простыми, их наибольший общий делитель равен единице. Выясним, как единица представляется в виде линейной комбинации соседних чисел Ферма.
Вот нужная нам функция.
FermatNumber[n_]:=2^(2^n)-N
Теперь можно написать и программу.
Do[Print[n,":",ExtendedGCD[FermatNumber[n+1], FermatNumber [n]]],{n,10}]
Результаты запишем в виде таблицы.
Заметьте, что в таблице при n>1 числа rn заканчиваются цифрой 8, а числа sn— цифрой 1.
Пример 6.8. Единица как линейная комбинация чисел 2n-1 и 2m-— 1 при взаимно простых пит. Так как числа 2n -1 и 2m -1 взаимно просты, если взаимно просты n и m, то единицу можно представить в виде линейной комбинации чисел 2n -1 и 2m-1 при взаимно простых пит. Выясним, до какого номера n(предполагая, что т<п) система Mathematica сможет в приемлемое время проверить взаимную простоту этих чисел.
Вот нужная нам функция.
fn[n_]:=2^n-1
Теперь можно написать и программу.
Do[ Dot If[GCD[n, m]==l, Print[n,":",m, ":", ExtendedGCD[fn[n],fn[m]]]],{m,n-l}],(n,10}]
Результаты запишем в виде таблицы .
Заметьте, что довольно часто в данной таблице встречается пара r = 1,5= -2. Это не случайно, поскольку при n = n+1 выполняется равенство -(2n -1)+2-(2(n -1) = -1.
Пример 6.9. Линейное представление наибольшего общего делителя чисел, десятичная запись которых состоит из m единиц и n единиц. Наибольший общий делитель чисел, десятичная запись которых состоит из т единиц и п единиц, является числом того же вида, причем количество единиц в нем равно d = НОД(n, m). Выясним, как он представляется в виде линейной комбинации.
Вот нужные нам определения.
a111[n]:=(10^n-1)/9 d: = GCD[n, m]
Теперь можно написать и программу:
Dot Dot Print[n,":",m,":", ExtendedGCD[alll[n],alll[m]]],{m,n-l}],{n,10}]
Заметьте, что десятичная запись чисел r и s в данной таблице содержит только цифры 0 и 1. Я не удивлюсь, если вы предположите, что это связано с наличием некоторых полиномиальных тождеств и потому значения г и s получаются в результате подстановки 10 (основания системы счисления) в них. Например, строку таблицы
| 9 |
6 |
111 |
1 |
-1000 |
можно истолковать так:
Наибольший общий делитель — функция GCD
Наибольший общий делитель — функция GCDФункция GCD находит наибольший общий делитель в области целых, рациональных и гауссовых чисел.
Наибольший общий делитель в кольце целых чисел
Чтобы найти наибольший общий делитель чисел n1, n2, ..., можно использовать функцию GCD [ n1, n2, ...]. Вот примеры ее применения для нахождения наибольшего общего делителя двух чисел.
GCD[36,45] 9 GCD[2200 + 3, 3300 + 80] 349 а=177^5+30621*173^3-173^5 177309584821 b=173^5+30621*177^3-177^5+ 151037867129 С=173^4+30621^2+177^4 2814896923 GCD[a,b] 30637 GCD[а,с] 30637 GCD[b,c]30637
Пример 6.1. Графики функции GCD.
Давайте теперь построим несколько графиков функции GCD. Поскольку это функция двух аргументов, построим изображения поверхности z = GCDflntegerPart [x], IntegerPart [у] ]. Для этого используем функцию Plot3D.
Наибольший общий делитель
Наибольший общий делительДля нахождения наибольшего общего делителя чисел (целых, рациональных или гауссовых) в системе Mathematica предусмотрено две функции: GCD и ExtendedGCD.
Наименьшее общее кратное — функция LCM
Наименьшее общее кратное — функция LCMВо множестве всех кратных нескольких данных чисел всегда найдется такое, которое является делителем всякого другого общего кратного этих чисел: это — общее наименьшее кратное.
Функция LCM находит наименьшее общее кратное в области целых, рациональных и гауссовых чисел.
Алгебра в программе Mathematica
Частное при делении с остатком — функция Quotient
Частное при делении с остатком — функция QuotientЧтобы получить частное при делении (с остатком) л на т, нужно воспользоваться функцией Quotient [n,m]. Рассмотрим пример.
Quotient [16,5] 3
Для целых n и m выражение Quotient [n,m] равносильно Floor [m/n]. Однако n и т могут быть вещественными и даже комплексными числами.
Quotient[Е^10,ЕЛ8] 7 Quotient[Е^10+25*1,Е^8+41] 7-1
В случае вещественных чисел Quotient [n, m] — это такое целое число х, что d
Quotient[16,5,14]
0
Вот как можно найти частные от деления чисел 0, 1, 2, ..., 21 на 3.
Quotient[Range[0,21],3]
{0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7}
А вот частные, когда задан сдвиг 1.
Quotient[Range[0,21],3,1]
{-1,0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6}
А вот частные, когда задан сдвиг 2.
Quotient[Range[0,21],3,2]
{1,-1,0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6}
Пример 7.1. Графики функции Quotient.
Давайте теперь построим несколько графиков функции Quotient. Поскольку это функция двух аргументов, построим изображения поверхности z = Quotient [х, у]. Для этого используем функцию plot3D.
Деление с остатком
Деление с остаткомПри выполнении операции деления с остатком получается частное и остаток. Для нахождения частного и остатка в системе Mathematica предусмотрены функции Quotient и Mod.
Китайская теорема об остатках — функция ChineseRemainder
Китайская теорема об остатках — функция ChineseRemainderХитрый китаец Сунь Цю около 2000 лет назад (конечно, это могло быть и 200 лет до нашей эры, и 200 лет после начала нашей эры) открыл правило "гай-йен" ("большое обобщение"), которое является частным случаем целочисленного аналога интерполяционной формулы Лагранжа для полиномов. (Правда, примерно в то же самое время, в 100 г. н. э., греческий математик Никомах знал точно тот же частный случай.) Полностью формула была сформулирована и доказана впервые, по-видимому, в 1734 году Л. Эйлером. Сформулируем китайскую (или греко-китайскую, как назвал ее Акритас, автор одного из широко известных учебников по компьютерной алгебре?) теорему об остатках и укажем соответствующее правило (формулу).
Пусть m1, m2, ..., mr — попарно взаимно простые модули (попарно взаимно простые положительные целые числа), m = m1, m2, ... mr — их произведение, а а, u1, u2, ..., ur — произвольные целые числа. Тогда существует ровно одно целое число и, такое, что а
Корни в системе остаточных классов
Корни в системе остаточных классовЗадача о корзинке с яйцами представляет собой задачу о решении системы сравнений вида u=ui(modmi) с попарно взаимно простыми модулями mt. Конечно, она
допускает дальнейшие обобщения. Если не считать линейных сравнений и их систем, то наиболее простой из таких задач окажется задача об извлечении квадратного корня в системе остаточных классов, т.е. задача о решении сравнения хr = d (modn).
Критерии простоты чисел специального вида
Критерии простоты чисел специального видаРассмотренные числовые функции могут успешно применяться для проверки простоты чисел специального вида. С помощью числовых функций для чисел специального вида удается построить критерии, эффективность которых часто на несколько порядков выше, чем эффективность критериев для чисел произвольного вида. Данная тема необъятна, и ниже рассмотрены только самые простые примеры применения таких критериев.
Квадратный корень по модулю — функции SqrtMod и SqrtModList
Квадратный корень по модулю — функции SqrtMod и SqrtModListКонечно, квадратных корней в системе остаточных классов — решений сравнения х =d (mod n) — может быть более одного. Поэтому в системе Mathematica предусмотрено две функции для нахождения таких решений. Функция SqrtMod находит наименьший вычет, а функция SqrtModList — Список всех вычетов.
Наименьший квадратный корень по модулю — функция SqrtMod
Выражение SqrtMod[d, n] представляет собой наименьший неотрицательный квадратный корень из d по модулю n, т.е. такой наименьший неотрицательный вычет m, что m2sd(modn). Но это, конечно, в том случае, если такое т существует. Для этого d, понятно, должно быть полным квадратом по модулю и, т.е. символ Якоби .jacobiSymbol [d, n] должен быть равным 1. Это условие также достаточно, если и является простым числом. Для простых n система Mathematica использует алгоритм Шенкса (Shanks). Для примера найдем самое маленькое неотрицательное целое число, такое, что его квадрат равен 3 по модулю 11.
SqrtMod[3,11] 5
Этот результат легко проверить.
Mod[Range[11]^2,11]
{1,4,9,5,3,3,5,9,4,1,0}
Как видите, только квадраты чисел 5 и 6 по модулю 11 равны 3. Если квадратный корень из d по модулю п не существует, SqrtMod [d, n] останется невычисленным.
Остаток от деления — функция Mod
Остаток от деления — функция ModЧтобы получить остаток от деления n на m, нужно воспользоваться функцией Mod[n,m]. Наименьший возможный остаток в этом случае равен нулю, а наибольший... Как вы думаете, чему равен наибольший возможный остаток? "Конечно, m-1", — возможно, подумали вы. Ну, что же, я, конечно, приветствую ваши глубокие познания в теории чисел, ибо именно так написано во всех классических учебниках по этой дисциплине, если, конечно, именно в этом месте нет какой-либо досадной опечатки. Но должен вас разочаровать: вы не угадали. Зато, надеюсь, вам будет приятно узнать, что возможности функции Mod значительно шире, чем требуется для решения задач из задачников по классической теории чисел. Дело в том, что аргументы этой функции могут быть не только целыми (это предусмотрено классическими учебниками теории чисел), но и вещественными и даже комплексными! А во множестве вещественных чисел, как вы, надеюсь, еще помните, полно сюрпризов... Но сначала давайте рассмотрим простейший случай целых аргументов.
Mod[7,5]
2
Ну вот, при делении 7 на 5 остаток равен 2. Просто и понятно, даже в уме можно вычислить. Вот еще один пример.
Мод[3^10,5]
4
Тоже в уме, и тоже просто и понятно. Но вот несколько примеров с вещественными числами.
Первообразные корни по модулю n
Первообразные корни по модулю nПоказатели — функция MultiplicativeOrder
Наименьшее натуральное решение т показательного сравнения km =1(modn) называется показателем числа k по модулю п. (Иногда это выражают иначе: говорят, что k принадлежит показателю т по модулю n.) В этом случае можно сказать, что k является корнем m-й степени из единицы в кольце классов вычетов по модулю т. Вот пример: 2 принадлежит показателю 4 по модулю 5.
Table[Mod[2го, 5], {m, 10}]
{2,4,3,1,2,4,3,1,2,4}
Для вычисления показателя т в системе Mathematica предусмотрена функция
MultiplicativeOrder[k, n].
MultiplicativeOrder[2,5] 4
Конечно, показатели существуют не во всех случаях, а только тогда, когда k ч п взаимно просты. Если показатель не существует, функция MultiplicativeOrder [k, n] остается невичисленной.
Функция MultiplicativeOrder может иметь еще третий параметр — список. Список {а,, а,,..., as} в вызове MultiplicativeOrder [k, n, {а,, а,, ..., as } ] используется тогда, когда нужно найти наименьшее т, удовлетворяющее хотя бы одному из сравнений km =a, (mod/i). 3 является наименьшим натуральным числом, удовлетворяющим хотя бы одному из сравнений 2m =5 (mod n) и 2m =8(modn).
Table[PowerMod[2,m,11],{m,10}]
{2,4,8,5,10,9,7,3,6,1}
Вот как это можно вычислить.
MultiplicativeOrder[2,11,{5,8}]
3
Пример 7.6. Длина периода систематической дроби по основанию b. Вот функция, которая вычисляет длину периода систематической дроби, представляющей рациональное число r по основанию b.
DigitCycleLength[r_Rational,b_Integer?Positive]:= MultiplicativeOrder[b,FixedPoInt[Quotient[#,GCD[#,b]]&, Denominator[r]]]
Вот пример. Длина периода дроби 1/49 в десятичной системе равна 42.
DigitCycleLength [1/4.9,10]
42
А вот и подтверждение.
N[1/49,151] 0.020408163265306122448979591836734693877551 020408163265306122448979591836734693877551 020408163265306122448979591836734693877551 02040816326530612244897959
Что такое первообразный корень по модулю n
Решая сравнение km =l(modn) относительно k, можно заметить, что при некоторых n находятся такие k, которые принадлежат довольно большим показателям m. В частности, при некоторых n случается, что k принадлежит показателю, который равен числу вычетов, взаимно простых с n. Такие числа k называются первообразными корнями по модулю n. Конечно, по составному модулю в большинстве случаев первообразных корней не существует. Первообразные корни существуют только по модулям 2, 4, рi и 2 рi (здесь р — произвольное нечетное простое число). Для вычисления первообразных корней по модулю и в системе Mathematica предусмотрена функция PrimitiveRoot [n].
PrimitiveRoot[5]
2
Если первообразного корня не существует, функция остается невычисленной.
PrimitiveRoot[11*13] PrimitiveRoot[143]
Следует помнить, что PrimitiveRoot использует Factorinteger как подпрограмму, так что она может не справиться с вычислениями в случае очень большого параметра.
Простые числа Мерсенна тест ЛюкаЛемера
Простые числа Мерсенна, тест Люка-ЛемераНаибольшее простое число поймано решетом Эратосфена.
Конечно, решето Эратосфена годится для поиска простых чисел Мерсенна не более чем консервная банка для плавания через Атлантический океан. Гораздо более пригодна для этой цели функция PrimeQ. С ее помощью мы нашли все те индексы простых чисел Мерсенна, которые не превышают 5000. Дальнейшее продвижение оказалось практически невозможным. Однако есть другой метод проверки простоты чисел этого вида. Его опубликовал Э. Люка (Lukas2) в 1878 году, а в 1930 году усовершенствовал Д. X. Лемер. Он основан на следующей теореме.
Если р>2 — простое число, то число Мерсенна Мр = 2p -1 является простым тогда и только тогда, когда bр_r = О, где последовательность L; определяется так:
L0 =4, Li+1=(Li2-2)mod(2i-l).
Совершенно элементарное доказательство этой теоремы имеется во многих книгах; в частности, его можно найти во втором томе трехтомника Кнута. Чтобы сократить доказательство, можно также заметить, что критерий Люка основан на малой теореме
Ферма для чисел из полей Q(v5) или Q(v3). Тест Люка позволил проверить вручную все простые числа до МР7. Когда для проверки простоты стали применяться ЭВМ, началась настоящая гонка. Очередные новые простые числа Мерсенна рассматривались как свидетельство быстрого роста возможностей ЭВМ. Чтобы убедиться, что Л/819] является составным, Д. Дж. Уилер потратил около 100 часов машинного времени ILLIAC I — самой быстрой ЭВМ выпуска пятидесятых годов. Гурвицу на IBM 7090 для этой же цели потребовалось лишь 5 часов в 1962 году. В 1964 году Гиллис сделал это на ILLIAC II за 49 минут. А в 1971 году Такерман потратил на это только 3 минуты на IBM 360/91. (Но то были суперЭВМ, а я на своем весьма слабеньком ПК на это потратил 4,125 секунды.) Проверка простоты М1тз на ILLIAC II заняла 2 часа 15 минут, и всего лишь 8 минут на IBM 360/91. (Но это столько нужно суперЭВМ, а моему старенькому ПК нужно всего лишь 9,672 секунды.) Найденное очередное простое число Мерсенна становилось визиткой фирмы. Например, доказательству простоты числа
М112,з Иллинойский университет посвятил выпуск фирменного конверта. IBM в долгу не осталась: она выпустила конверт, посвященный доказательству простоты М19937 (это 6002-значное число, найденное Б. Такерманом 4 марта 1971 года, довольно долго было рекордсменом). Проверка простоты этого числа и у меня заняла изрядное время - 42 094 секунды. с помощью функций Mod и powerMod несложно запрограммировать тест Люка- Лемера. Сначала дадим нужные определения.
Mn[n_]:=Module[{t=4}, Do[t=Mod [PowerMod[t, 2,mn] -2,mn],
Block[{p=3}, While [p<45000, {If[MPrime[р],Print[p]], p=NextPrime[p] } ] ]
Даже на весьма слабеньком компьютере всего за несколько часов вы можете найти все нечетные индексы р первых 24 простых чисел Мерсенна известных до 1980 года: 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937. Здесь, конечно, только 23 числа, поскольку индекс первого простого числа Мерсенна М2 = 3 четный: р = 2.
Надеюсь, вы о нем не забыли, так что не забудьте и отпечатать специальные конверт. Заметьте что данную программу очень легко распараллелить и организовать поиск на нескольких ЭВМ. Кроме того, данную программу легко модифицировать так, чтобы поиск продолжался после уже проверенных чисел. Впрочем, возможно, программу придется модифицировать так, чтобы она время от времени подавала признаки жизни", даже если не успевает найти простое число Мерсенна. Это можно сделать, например, так.
Block[{р=19937,1=1},p; While [p<45000, {If [MPrime [p], Print [p]], p=NextPnme [p] , If[Mod[i++,500]==0, Print["***p=",p]] HI
Так что если не поленитесь потратить ночку-другую на вычисления, то найдете и другие простые числа р, при которых р-е число Мерсенна Mf = 2'-l является простым. В частности, вы сможете найти 6533-значное простое число Мерсенна Л/,,70, (найдено калифорнийскими школьниками Никкелом и Ноллом в 1978 году), 6987-значное простое число Мерсенна М23209 (найдено Ноллом), 13395-значное простое число Мерсенна Мш„ (это 27-е простое число Мерсенна найдено Д. Словинским в 1979 году), 25962-значное простое число Мерсенна М86243 (это число Мерсенна найдено Дэвидом Словинским в январе 1983 года). Если хотите, проверьте, не пропустил ли я чего-нибудь и сможете ли вы продвинуться дальше. У меня проверка простоты М,1701 заняла 53,547 секунды, М2Ш) - 64,25 секунды, Мшу, - 350,562 секунды (ого, почти 6 минут!), Мим - 1845,34 секунды (это чуть больше получаса). Думаю, что дальнейшее продвижение по данной программе весьма затруднительно. В данном случае либо нужен компьютер со значительно более высоким быстродействием, либо нужно изменить программу так, чтобы большинство составных чисел отсеивалось еще до применения критерия Люка. Казалось бы, перед применением критерия Люка можно проверить, что число Мр не удовлетворяет сравнению ам' = a(modMp) при некоторых а. В качестве а удобно взять, например, число 3. Можно было бы также попытаться проверить другое свойство простых чисел. Однако при этом нужно тщательно следить за тем, чтобы все эти дополнительные проверки не снижали быстродействие программы. Время проверки сравнения an s=a(modMp) может оказаться, например, примерно равным времени проверки по критерию Люка—Лемера. Тогда, понятно, такая дополнительная проверка только замедляет выполнение программы. Так что дальнейшее продвижение требует изобретательности.
Дальше идет степень 110503. В 1983 году была найдена степень 132049, а в 1984 — 216 091. Поиском степеней на суперкомпьютерах прославился в 90-х годах XX столетия Дэвид Словинский. Вместе с Полем Гейджем он получил следующие индексы простых чисел Мерсенна: 756 839, 859 433, 1 257 787. Но степени 1 398 269 и 2 976 221 были найдены Жоэлем Арменгодом (Joel Armengaud) и Гордоном Спенсом (Gordon Spence) на персональных компьютерах по программе, разработанной Георгом Вольтманом (George Woltman) в 1996 году. Предварительная проверка Л/2,76,,, на компьютере с процессором Pentium с тактовой частотой 100 МГц заняла 15 суток в августе 1998 года! 27 января 1998 года Роланд Кларксон (Roland Clarkson) обнаружил простоту Л/3021377, а 1 июня 1999 года Найян Хьяратвала (Nayan Hayratwala) — простоту Af6972593. Впрочем, люди стремятся к рекордам, и после 1983 года числа проверялись не подряд, так что могли что-то и пропустить! Правда, добровольцы тщательно потом все просмотрели до миллиона!
Как из этого видно, критерий Люка—Лемера применяется только после некоторого предварительного отбора, которому уделяется огромное внимание. Давайте попробуем найти хотя бы какой-нибудь очень простой (а, значит, и довольно грубый) метод отсева показателей р, для которых числа Мерсенна Мр не являются простыми. Пусть s— показатель 2 по некоторому простому модулю q: Т =1 (mod q). (Такое 5 можно найти с помощью функции MultiplicativeOrder [2, q].) Поскольку Мp = 1n -1 оно делится на простое число q, если р является показателем 2 по простому модулю q. Так что такие индексы р чисел Мерсенна можно отсеять сразу, если Мр # q. Поэтому для предварительного отсева нам понадобится таблица показателей 2 по простым модулям q. Причем, чтобы уменьшить таблицу, из нее можно вычеркнуть все составные показатели. Чтобы построить таблицу, нам понадобится следующая функция.
f[n_]:= Block[{q= Prime[n], s=MultiplicativeOrder[2,q]}, If[NumberQ[s],If[PrimeQfs],s]]]
Эта функция по заданному номеру n находит простое число q = рn, а затем — 5 (показатель 2 по найденному простому модулю q, если он существует). Если оказывается, что показатель 2 по простому модулю q существует, проверяется, является ли он простым числом. Если оказывается, что найденный показатель 2 по простому модулю q является простым числом, он возвращается в качестве значения функции. (В противном случае функция возвращает Null.) С помощью этой функции легко строится нужная нам таблица простых показателей 2 по простым модулям q.
t=Union[Sort[DeleteCasestArray[£,100000, 4] ,Null]]] ;
Функция Array [f, 100000, 4] генерирует следующий список из 100000 элементов {f[4], f[5],...}- Функция DeleteCases [Array [f ,100000, 4] ,Null] удаляет из него элементы, равные Null. Затем функция Sort сортирует этот список, а функцияUnion рассматривает его как множество и тем самым исключает из него повторяющиеся элементы.
Из массива, который первоначально содержал сто элементов, получается список всего из 15 элементов.
tl=Union[Sort[DeleteCases[Array[f,100,4],Null]]]
{3,5,7,11,23,29,37,43,73,83,131,179,191,239,251}
Понятно, что это очень мало. Но даже если бы мы исходили из тысячи простых чисел, у нас бы получился список из 80 элементов.
существует весьма эффективный критерий
Простые числа вида k*2n +1Для чисел вида k*2n+ 1 существует весьма эффективный критерий простоты. Он состоит в проверке сравнения а2n-1 =-1 (mod k*2n +1) для некоторого а. Однако выбор этого а зависит от k. Оказывается, нужно различать случаи, когда k не делится на 3 и делится на 3. Случай, когда k не делится на 3, совсем прост.
Случай, когда k не делится на 3
Если k не делится на 3, то, как заметил Прот (Proth) в 1878 году, числа k*2n +1 являются простыми при kn + 1 тогда и только тогда, когда 32n-1-1 (mod k-2n+l). Впрочем, эта традиционная формулировка критерия Прота несколько некорректна. В ней, например, (молчаливо!) исключается случай n = 1, k = 1. Для n =1, k - 1 имеем k = k3 = 2+1= 2" + 1, хотя З2""* =3sO (mod /n2n+1), причем *-2"+1 =3-простое число. Дело в том, что если число k-2n +1 простое, то в традиционной формулировке критерия Прота число3 должно быть квадратичным невычетом по модулю k-2n + l. Но при и= 1, k= 1 число k2n+l =3. Впрочем, n- 1, k- 1 — единственное решение уравнения k* 2n +1 =3 в целых числах, отличных от 0. (Уравнение k-2" + 1 =3 в целых числах имеет всего два решения: указанное только что решение n= 1, k= 1 и n = 0, k= 2.)
Разыскивая простые числа вида k*2n +1, конечно, нельзя ограничить перебор по и только простыми числами, но все равно многие значения отсеиваются тривиальным образом.
Пример 7.7. Простые числа вида 5-2n + 1. Рассмотрим, например, случай k = 5. Тогда числа вида 5*2n +1 делятся на 3 при четных п. Так что перебор можем вести только по нечетным и.
Используя функцию PowerMod, очень легко запрограммировать критерий простоты.
MknPrime[k_,n_]:=Module[{t = k*2An+l},
If[k<=2An+l,PowerMod[3,(t-1)/2,t]==t-l,PrimeQ[t]]]
А вот и программа для перебора по нечетным п.
Mkn[k_,nl_]:=Block[{n=l},
While [n<=nl, {If[MknPrime[k,n],Print[п]], n+=2}]];
Теперь можем выполнить перебор. Mkn[5,300000]
Так можно получить (если хватит терпения) следующие значения я: 1, 3, 7, 13, 15, 25, 39, 55, 75, 85, 127, 1947, 3313, 4687, 5947, 13165, 23473, 26607, 125413, 209787, 240937.
Впрочем, при дневном счете терпение обычно улетучивается после печати числа 13165, если не раньше. Конечно, метод перебора можно усовершенствовать, заметив, что если остаток от деления и на 3 равен 2, то число 5*2n +1 делится на 7. Так что числа, дающие в остатке 2 при делении на 3, можно при переборе пропустить. Можно также пропустить числа, дающие в остатке 1 при делении на 10, поскольку тогда число 5*2n + 1 делится на 11. Можно, конечно, пойти и дальше. Можно, например, взять несколько небольших нечетных простых чисел д, для которых существует решение сравнения 5-2n + 130 (mod q). Пусть s— показатели 2 по модулю q: 2s=1 (mod q). (Такое 5 можно найти с помощью функции MultiplicativeOrder [2, q].) Тогда при всех n^t (mod s) 5*2n + 1 = 0 (mod q). Если q не является числом вида 5*2n +1, все числа nst (mod s) можно опустить при переборе. Если же q является числом вида 5*2n +1, то нужно оставить только то число rmt (mod s), при котором 5*n + 1 = q. Эта идея вполне реализуема, но не слишком ли она усложняет перебор?
Давайте попробуем. Вот функция, которая по заданному номеру я простого числа q находит t — решение сравнения 5* 2n +1 = О (mod q) и i — показатель 2 по модулю q, если такое решение существует.
:[n]:= 51ock[{q= Prime[n], s=MultiplicativeOrder[2,q], t=MultiplicativeOrder[2,q,{-PowerMod[5,-I, q]} ] }, If[NumberQft],fs,t}]]
Теперь с помощью этой функции можно сгенерировать таблицу остатков и соответствующих им модулей.
Возведение в степень в модулярной
Возведение в степень в модулярной арифметике — функция Power ModИногда приходится решать задачи такого типа:
Конечно, совсем несложно написать что-нибудь вроде Mod[a^b,n] или Моd[а^b, с^m]. Однако все дело в том, что в исследовательских задачах b может быть столь велико, что для вычисления аb не хватит памяти. Кроме того, по мере вычисления аb часто бывает так, что требуется все больше памяти и начинает работать подкачка, что очень часто приводит к пробуксовыванию. А тогда процессор практически простаивает, и даже самая простая операция выполняется фантастически долго.
Пример 7.3. Наибольшее число, которое можно записать тремя цифрами. Число 999 имеет 369 693 100 цифр, т.е. более трети миллиарда! Еще в 1953 году было известно, что это число начинается цифрами 428 124 773 175 747 048 036 987 115 930 563 521 339 055 482 241 443 514 174 753, а заканчивается цифрами 24178799359681422627177289. Какие цифры между ними, не было известно и в 1959 году. Ведь если это число напечатать более или менее четко на полоске бумаги, то эта полоска оказалась бы длиной 1200, а может и 1800 км. Если же напечатать это число в книге так, чтобы на каждой странице помещалось 14 000 цифр (на странице обычно помещается 2,5—3 тысячи знаков), то такая книга состояла бы из 33 томов по 800 страниц в каждом. Но с помощью системы Mathematica несложно вычислить, например, первую и последнюю тысячу цифр числа 999. Чтобы вычислить первую тысячу цифр числа 999, нужно просто вычислить это число с разрядностью не менее тысячи знаков. Вот как это делается.
М[9^(9^9),1000] 4.281247731757470480369871159 30563521339055482241443514174753723053523 887471735048353193665299432033375060417533 64763100078032613904733860832080206037470612 809165574132086446019861999614520310524428581489598115 1471949351767796559302159393385015023969426231 0529675816569433334631474925538494859337781208762 495721650419522060180457130151786405101459407 904194866332733667183065441076023482363342793388473 449171490713928387636703470733221615842638847026446 505858035582482311577827786618011472099436290690473438 366488664695023381735331493288811517612485971201533575 64439876059956217339548503950536965544532955477621833381 799037537429866036175410766960904718339923933145342547022 698333065128258703520736236 343330809161939992399143539 9517426262619225044491488935534629633876424, 710803619094832833935338326811681684096752173716022 71240386424109448631241673361631602584738577273169933875 567294188775379238762791518151971 69574861839692092170993 60780264476440839592643445485180078094839593328 539827016475025109538Х10369693099
Почти так же можно вычислить и последнюю тысячу знаков.
Mod[9^(9^9),10^1000]//Timing{260.64 Second, 164378947574778447311427807670372670 0326359025082234292387746462391127 9751529028988405927046285969119001418 842032015433264756391857718597649 204912230323811027210136918 3684943285741373762637969125845614123744406 01020026085922354 10622770718702230402359356419151296996286668460066302 9835137 9027215796574565344432784903341994543575575416975966278964106 12 7038799025612835366795058993611717249028581457173391518760 2283281383558665788995350272253954345165983917336427507154331 749386377957650223307 168958637197192110578737857336943212457 7155212755139983177854767167859 12996450672962748373653022152 34320507478340927905653712738326405359097 6996351343597753799 283680752817548382724478144536940979972304718417625 894479515 4018072624283659761429188348967918815377285476781074966161266 1854762666853235529005571888491679885547006847358268508973918 700851075402818853925349052912288203971972 4032235787006073283877358282 617004315060225040660196165699439754361026855266374036682906 1901749234943241787 99359681422627177289}
Вычисление, как видите, заняло более четырех минут (260,64 секунды). Но гораздо быстрее результат можно получить вот так.
PowerMod[9,9^9,10^1000]//Timing {0.015 Second, 1643789475747784473114278076703726700...2627177289}
(Здесь середина пропущена.) Это вычисление заняло лишь 0,015 секунды. Это более чем в тысячу (точнее, в 17376) раз быстрее!
Пример 7.4. Графики функции Power Mod.
Давайте теперь построим несколько графиков функции PowerMod. Поскольку это функция двух аргументов, построим изображения поверхности z = PowerMod[x, у]. Для этого используем функцию Plot3D.
Алгебра в программе Mathematica
Функции связанные с делителями — Divisors и DivisorSigma
Функции, связанные с делителями, — Divisors и DivisorSigmaДелители натурального числа легко найти с помощью системы Mathematica. Для этого предусмотрена функция Divisors. Найдем, например, делители 120.
Divisors[120] {1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120}
Эта функция работает и в области гауссовых чисел.
Divisors [24 + 301.] (1,1+I,2,3,3+3I,4+5I,6,8+10I,9+11I,12+15I,24+30I,27+31I}
При необходимости нужно указать опцию Gaussianlntegers->True. Без этой опции делители натуральных чисел находятся только среди натуральных чисел.
Divisors[320] {1,2,4,5,8,10,16,20,32,40,64,80,160,320}
Если же указать эту опцию, то даже у натурального числа будут найдены все его делители в области гауссовых чисел.
Функция Эйлера — EulerPhi
Функция Эйлера — EulerPhiЕсли в полной системе вычетов по модулю nоставить только вычеты, взаимно простые с модулем, получим приведенную систему вычетов по модулю n. Мощность приведенной системы вычетов по модулю n как множества обозначается ?(n), а функция ?:n->?(n) называется функцией Эйлера. Найдем, для примера, приведенную систему вычетов по модулю 10.
Select[Range[10],GCD[fl,10]==!&] {1,3,7,9}
Приведенная система вычетов по модулю 10, как видим, содержит 4 элемента. Значит,?(10) = 4. В системе Mathematica функция Эйлера имеет имя EulerPhi. Вот как можно вычислить ?(10).
EulerPhi[10] 4
Функция Эйлера имеет замечательные свойства и многочисленные применения. Например, она обладает следующим свойством:
Если а и т взаимно простые, то а?(m) = 1(modm).
Это утверждение называется теоремой Эйлера и очень часто малой теоремой Ферма, который знал ее частный случай для простых модулей т. Эта теорема позволяет упростить вычисление остатков степеней чисел, взаимно простых с модулем. Рассмотрим пример.
Пример 8.1. "Бытие Бога". Во второй половине XIX века некоторых авторов привлекали числа 22, З3 , 44 . Вот что пишет об этих числах известный немецкий популяризатор математики Вальтер Литцман в середине XX столетия:
В одной, изданной в 1874 году книге под названием "Бытие Бога" (автор книги — Крениг) рассматривается ряд чисел: 22, З3 , 44 .О последнем из этих чисел автор говорит: "Представьте себе отрезок такой длины, что световому лучу понадобился бы квинтиллион лет, чтобы пройти этот путь. Затем представьте себе шар с диаметром, равным этому отрезку, наполненный типографской краской. Всей этой краски не хватило бы, чтобы четко напечатать это число даже самыми мелкими цифрами, какие только существуют". X. Маурер исследовал эти числа с точки зрения теории чисел. Обозначив для простоты число Xх через 3x: и введя затем общее обозначение nх = хm (где хил — целые положительные числа), он показал, как можно найти последние цифры этих числовых великанов. Так, например, 29 (т. е. 99) оканчивается на 89, 39 — на 289, 49 — на 5289, 59 — на 45 289 и так далее, наконец, 109 — на 9 392 745 289. Таким образом, последние n цифр числа "9 повторяются во всех последующих числах "+19, "+29 , ... и т.д. Аналогичными свойствами обладает и любой другой ряд 1х = х, 2х , 3х, ... и так далее, где х — целое.
Что вы чувствуете по мере чтения этого отрывка? Я чувствую интерес и нарастающее недоверие. Я, например, в захвате от сравнения с шаром. Но я сомневаюсь, заканчивается ли 109— на 9 392 745 289. И даже если последние и цифр числа "9 повторяются во всех последующих числах "+19, "+29, ... и так далее, то я полагаю, что это как-то связано с девяткой и с тем, что эти числа записываются в десятичной системе счисления. Едва ли такими свойствами обладает и любой другой ряд 1х = х, 2х , x , ... и так далее, где х — целое. И действительно, i2 = 2 заканчивается на 2, а 2 х = 4 — на 4. Уже последняя цифра не повторяется во всех последующих числах этого вида! Как можно говорить о повторении последних n цифр числа? Так что насчет таких свойств у любого другого ряда 1х = х, 2х , 3x... и так далее, где х — целое, то тут явное вранье. Вальтер Литцман, правда, говорит не о таких свойствах, а об аналогичных свойствах, но в чем отличие, не указывает явно. Такими свойствами не обладают, например, числа х = 3, 4, 8 и многие другие. Поэтому в чем именно состоит аналогия, для меня пока не совсем понятно. И мне, естественно, хочется прояснить этот вопрос и еще сильнее хочется вычислить последние и цифр числа n9.
Давайте начнем с вычисления последних n цифр числа n9. Как это сделать с помощью системы Mathematica?
Вот определение функции nх .
GodF[n_,x_]:=Module[{t=1},Do[t=xAt,[i,n}];t]
Функция "х возрастает очень быстро, значительно быстрее факториалов, поэтому, если нужно вычислить, скажем, последние k знаков какого-нибудь значения этой функции, необходимо использовать PowerMod.
GodFLastk[n_,x_,k_] := If [n==l,Mod[x,10Ak],PowerMod[x,GodF[n-l, х],IQ^k] ]
Пусть k = 50. Тогда мы в мгновение ока сможем вычислить последние 50 знаков чисел 19, 29 и 39. Но вот вычислить последние даже 10 знаков числа 49 так легко не удастся. Этот пример показывает, что в некоторых случаях применение функции PowerMod может продвинуть вычисления всего лишь на один шаг!
Но функция Эйлера (и малая теорема Ферма) позволяет быстро вычислить последние 50 знаков числа "9. Программа, конечно, будет другая.
PowerMod[9,PowerMod[9,9A9,EulerPhi[10^50]],1^50] 30363975097419408973491530163140828233401045865289
Можно ли быстро вычислить последние 50 знаков числа 59 по такой программе?
PowerMod[9,PowerMod[9,9Л9Л9,EulerPhi[10Л50]],10^50]
Едва ли.
В чем же причина такого медленного продвижения, почему мы продвигаемся только на один шаг? Это происходит потому, что мы на самом деле устраняем быстрый рост функции nx = x(nf} только на последнем шаге. Почему это происходит? Потому, что мы все время связаны с определением функции GodF. Именно она используется внутри функции GodFLastk. Даже фактически отказавшись от явного применения функции GodFLastk, мы все равно стремимся записать выражение для nх = х(nn) с некоторыми упрощениями для последнего или предпоследнего возведения
в степень. Конечно, это так естественно использовать выражение для "х = х(') Однако нужно иметь в виду, что использование подобных "прямолинейных" определений часто весьма неэффективно. Если уж мы решили повышать эффективность, то делать это нужно на всю "глубину" выражения. Правда, это неизбежно приведет к появлению новых функций. Нам, например, придется отказаться от функции GodFLastk. Как ни удивительно, но вместо нее нам понадобится только одна функция, притом довольно простая. Давайте найдем ее определение. Обозначим через С(n, х, k) остаток от деления "х на k. (Таким образом, G(n, х, m) — это последние т цифр числа nх .) Тогда 0(1, х, k) = Mod [х, k]. С другой стороны,
С(n+1,x,k)=Mod[ хn,k]=PowerMod[x,"x ,k].
Предположим теперь, что х и k взаимно просты. Тогда по малой теореме Ферма это выражение можно записать так: PowerMod [x, G(n, х, ср(А:)), k]. Так что в этом случае G(n+l, x, k) = PowerMod [x, G(n, x,
Теперь легко написать программу.
Do[Print["n=",n,":",GodFk[n,x=9,10/sk]],{n,k=50}]
Давайте теперь выполним аналогичные вычисления для числа 3. Вот так запишется программа.
Do[Print["n=",n,":",GodFk[n,x=3,10Ak]],{n,k=50}]
Теперь понятно, что имел в виду Вальтер Литцман под аналогичными свойствами. Начиная с некоторого и = и„ последняя цифра числа не изменяется, причем начиная
с и = "() + 1 повторяются уже две цифры, с n = n0+2 — три цифры, с n = n0+k — k цифр и т. д. (Через и„ (х) удобно обозначать наименьшее п0 с таким свойством.) Для некоторых х, например для х = 9, n(х) = 1, а для некоторых х (n)>1. Если п0(х)>1, то нельзя утверждать, что последние n цифр числа "х повторяются во всех последующих числах "+1x, "+2х, ... и т.д. Если п0(х)>1, то повторение последних nцифр начнется не с числа "х, а несколько позднее! Да уж, разбираться в популярных книжках иногда приходится с системой Mathematical
Пример 8.2. График функции Эйлера.
Давайте теперь построим график функции Эйлера. Сначала используем функции Table и EulerPhi для построения таблицы tl (точнее, списка) значений функции Эйлера.
t1= Table[EulerPhi[k],{k,1,n=10A3}];
Теперь можем использовать функцию ListPlot для построения графика.
Функция Мебиуса µ(m) — MoebiusMu
Функция Мебиуса µ(m) — MoebiusMuФункция Мебиуса µ(m) = 1, если т есть произведение четного числа различных простых чисел; µ(m) = -1, если m есть произведение нечетного числа различных простых чисел; (f(/n) = 0, если т делится на квадрат какого-либо простого числа. Вот как вычисляется эта функция.
MoebiusMu[210] 1
Пример 8.4. График функции Мебиуса.
Давайте теперь построим график функции Мебиуса. Сначала мы используем функции Table и MoebiusMu для построения таблицы tl (точнее, списка) значений функции Мебиуса.
tl= Table[MoebiusMu[k], {k,1,п=10^3}];
Теперь можем использовать функцию ListPlot для построения графика.
Биржевой анализ: Технический анализ - Инструменты - Софт
- Биржевой анализ - Технический анализ
- Обучение техническому анализу
- Индексы технического анализа
- Индикаторы технического анализа
- Методы технического анализа
- Графика в техническом анализе
- Технический анализ рынков
- Российский технический анализ
- Инструменты технического анализа
- Математика в биржевом анализе
- Разновидности биржевого анализа
- Mathematica в биржевом анализе
- MathCAD в биржевом анализе
- Maple в биржевом анализе
- Matlab в биржевом анализе