Расширение в теории чисел
Мы уже описывали уникальные возможности систем Mathematica 3/4 в области обработки чисел и численных вычислений. Эти возможности существенно расширяет пакет NumberTheory, содержащий функции, реализующие алгоритмы теории чисел. Данный раздел посвящен знакомству с этим пакетом.
Цепные дроби — ContinuedFractions
Следующие функции подпакста ContinuedFractions служат для представления чисел в виде цепных дробей или для формирования цепной дроби из списков:- ContinuedFraction [х] — возвращает цепную дробь для рационального числа х;
- ContinuedFraction [х, n] — возвращает цепную дробь для числа х с числом членов п;
- ContinuedFractionForm [{а0, al,...}] — создает цепную дробь из списка {a0,al,...};
- Normal [ContinuedFractionForm[ {а0, al,...}]] — представление в нормальной форме.
Примеры разложения чисел на цепные дроби:
<<NumberTheory` ContinuedFractionss ContinuedFraction[123/1234]//ContinuedFractionForm ContinuedFraction[Sqrt[5], 10]//ContinuedFractionForm 2, ContinuedFraction[GoldenRatio, 6 ] //ContinuedFractionForm Table[ Normal[ContinuedFractionForm[Table[1, {n}]]], {n, 9}] %- N[GoldenRatio] {-0.618034, 0.381966, -0.118034, 0.0486327, -0.018034, 0.00696601, -0.00264937, 0.00101363,-0.00038693}В подпакете имеются также следующие функции:
- ToPeriodicForm[x] — дает десятичное представление для рациональнЪго числа 0 < х < 1;
- ToPeriodicForm [х, b] — дает представление рационального числа х числом с основанием b;
- PeriodicForm[ {а0,...}, {am,...}] — дает периодическую форму представления списков;
- PeriodicForm[ {а0,...}, {am,...},b] — дает периодическую форму представления списков с основанием b;
- Normal [ PeriodicForm [{а0,...}, {am,...}]] — преобразование в нормальную форму;
- Normal [PeriodicForm[ {а0,...}, {am,...} ,b] ] — преобразование в нормальную форму с основанием b.
ToPeriodicForm[ 1/50 ] 0.02 ToPeriodicForm[ 1/23 ] 0.0434782608695652173913 PeriodicForm[1,2,3,4] 0.1234 RealDigits[ N[ 1/23, 25 ] ] {{4, 3, 4, 7, 8, 2, 6, 0, 8, 6, 9, 5, 6, 5, 2, 1, 7, 3, 9, 1, 3, 0, 4, 3, 5}, -1} ToPeriodicForm[ 1/20, 2 ] 0.000011 ToPeriodicForm[ 1/127 ] 0.007874015748631496062992l2598425l968503937 Normal[%] 1/127В системе Mathematica 4 функция ContinuedFraction стала встроенной. Имеется также встроенная функция FromContinuedFraction [list], которая строит цепную дробь по элементам списка list.
Улучшенное разложение на простые множители — FactorlntegerECM
Алгоритм разложения чисел на простые множители, реализованный в ядре Mathematiica 3, способен за 3 часа (на рабочих станциях) разлагать числа, имеющие до 18 цифр. Улучшенный алгоритм в подпакете FactorlntegerECM позволяет увеличить максимальное число цифр до 40. Реализуется разложение следующей функцией:- FactorIntegerECM[n] — возвращает один из делителей числа п. Возможны опции FactorSize->q, CurveNumber->b и CurveCountLimit->c.
Примеры применения этой функции:
<<NumberTheory`FactorlntegerECM` FactorIntegerECM[123456789] 34227 3*5*7*9 945 FactorlntegerECM[945] 189
Функции теории чисел — NumberTheory Functions
В подпакете NumberTheoryFunctions имеется ряд функций, относящихся к теории чисел:- SquareFreeQ[n] — дает True, если п не имеет квадратичного фактора, и False в ином случае;
- NextPrime [n] — дает наименьшее простое число, превосходящее п;
- ChineseRemainderTheorem[listl, Iist2.] — дает наименьшее неотрицательное целое г, такое что Mod [r, Iist2] ==list1;
- SqrtMod [d, n] — дает квадратный корень из (d mod п) для нечетного n;
- PrimitiveRoot [n] — дает примитивный корень п;
- QuadraticRepresentation [d, n] — дает решение {х,у} для уравнения х 2 + (d у) 2 ==п для нечетного п и положительного d;
- ClassList[d] — дает список неэквивалентных квадратичных форм дискриминанта d для отрицательного и свободного от квадратов целого d вида 4n+1;
- ClassNumber [d] — дает список неэквивалентных квадратичных форм дискриминанта d;
- SumOf Squares [d, n] — дает число представлений целого числа п в виде суммы d квадратов;
- SumOf SquaresRepresentations [d, n] — дает список представлений целого числа п в виде суммы d квадратов, игнорируя порядок и знаки.
<<NumberTheory`NumberTheoryFunctions` SquareFreeQ[2*3*5*7] True SquareFreeQ[50] False NextPrime[1000000] 1000003 ChineseRemainderTheorem[{0, 1, 2}, {4, 9, 244 ChineseRemainderTheorem[Range[16], Prime[Range[16]]] 20037783573808880093 SqrtMod[3, 11] 5 SqrtMod[2, 10^64 +57] 876504467496681643735926111996 54610040103361197677707490912 2865 PrimitiveRoot[7] 3 QuadraticRepresentation[l, 13] {3,. 2} ClassList[-19] {{1, 1, 5}} ClassNumber[-10099] 25 SumOfSquaresRepresentations[3, 100] {{0, 0, 10}, (0, 6, 8}}
Работа с простыми числами-PrimeQ
В подпакете PrimeQ в дополнение к функции ядра PrimeQ [n] имеется ряд функций для работы с простыми числами:- ProvablePrimeQ [n] — возвращает True, если п проверено на простоту, и False в ином случае;
- PrimeQCertif icate [n] — возвращает сертификат о том, что n— простое или композитное число;
- ProvablePrimeQ [n, Certif icate->True] — возвращает сертификат, который может использоваться для проверки чисел на простоту;
- PrimeQCertif icateCheck [check, n] — проверяет, удостоверяет ли сертификат check простоту или композитность п.
<<NumberTheory` PrimeQ` PrimeQ[127] True ProvablePrimeQ[127] True PrimeQCertificate[127] {127, 3, {2, {3, 2, {2}.}, {7, 3, {2, {3, 2, {2}}}}}} ProvablePrimeQ[127, Certificate->True] (True, {127, 3, {2, {3, 2, {2}}, {7, 3, {2, {3, 2, {2}}}}}}} PrimeQCertificate[3511, SmallPrime -> 1000] {{CertificatePrime -> 3511, CertificatePoint->PointEC[2, 2467, 1447, 2135, 3511], Certif icateK-> 32, Certif icateM -> 3424, CertificateNextPrime -*107, CertificateDiscriminant -> -7}, 107, 2, {2, {53, 2, {2, {13, 2, {2, {3, 2, {2}}}}}}}}
Вычисление примитивных элементов — Primitive Element
Подпакет PrimitiveElement содержит всего одну функцию для вычисления примитивных элементов множественного алгебраического выражения:- PrimitiveElement [z, {а1„а2,...} ] — возвращает список {b, { f1, f2,...}}, где b — примитивный элемент расширения рациональных алгебраических чисел al, а2,... и f1, f 2,... — полином переменной z, представляющей al, a2, ... как термы примитивного элемента.
<<NumberTheory`PrimitiveElement` PrimitiveElement[z, {Sqrt[2], Sqrt[3]}] RootReduce[%[[2]] /. z -> %[[1]]]
Создание рядов Рамануджанат-Дирихле — Ramanujan
В подпакете Ramanujan определены следующие функции:- RamanujanTau [n] — n-й коэффициент ряда Рамануджана т-Дирйхле (т n );
- RamanujanTauGeneratingFunction [z] — производящая функция ряда Рамануджана т-Дирихле;
- RamanujanTauDirichletSeries [s] — ряд Рамануджана т-Дирихле f(s);
- RamanujanTauTheta [t] — функция Рамануджана т-Дирихле o(t)
- RamanujanTauZ [t] — функция Рамануджана т-Дирихле z(t).
<<NumberTheory`Ramanujan` RamanujanTau[5] 4830 Sum[RamanujanTau[n] z^n, {n, 5}] z - 24 z2 + 252 z3 - 1472 z4 + 4830 z5 RamanujanTauGeneratingFunction[. 1] 0.00610209 RamanuJanTauGeneratingFunction[.99] 4.10287803703 x -1673 RamanujanTauDirichletSeries[6 + 9.221] 0.00040309-0.002390131 z = RamanujanTauZ[9.22] 0.00242388 theta = RamanujanTauTheta[9.22] 1.40372043366323 z Exp[-I theta] 0.00040309 - 0.00239013 I
Рационализация чисел — Rationalize
Подпакет Rationalize расширяет возможности представления чисел в рациональном виде. Он содержит определения следующих функций:- ProjectiveRationalize [ {х0, xl,..., хn} ] — возвращает список целых чисел, дающих рациональные представления для чисел заданного списка;
- ProjectiveRationalize [ {х0, xl,..., хn} ,ргес] — возвращает список целых чисел, дающих рациональные представления с погрешностью не более 10- рreк
- Af f ineRationalize [ {х0, xl,..., хn} ] — возвращает список рациональных приближений для чисел заданного списка;
- Aff ineRationalize [ {х0, xl,..., xn} ,prec] — возвращает список рациональных приближений для чисел заданного списка, вычисленных с погрешностью не более 10- ргес .
<<NumberTheory` Rationalize` Rationalize[N[3 Pi], 6]/ Rationalize[N[11 Pi], 6] 9/35 ProjectiveRationalize[{N[3 Pi], N[11 Pi]}] {3, 11} AffineRationalize[{N[3 Pi], N[11 Pi]}, 6] {1065/113, 3905/113 }
Нахождение полинома, дающего заданный корень — Recognize
Подпакет Recognize содержит определение одноименной с ним функции в двух формах:- Recognize [x,n,t] — находит полином переменной t степени, большей п, такой, что х является его корнем;
- Recognize [х, n, t, k] — находит полином переменной t степени, большей п, такой, что х является его корнем, и со штрафным весовым коэффициентом k, предназначенным для подавления генерации полиномов высших степеней.
<<NumberTheory`Recognize` NSolve[2 x^3- x + 5 == 0] {{x->-1.4797}, {x-> 0.739852-1.068711}-, {x->0.739852+ 1.068711}} sol = First[x /. %] -1.4797 Recognize[sol, 3, t] 5-t+2t3 Recognize[sol, 2, t] -225599 - 1464961 + 4032 t2 Recognize[N[Sqrt[3^(2/5)]], 5, t] -3+t5 Recognize[N[Sqrt[3A(2/5)]], 5, t, 10] -14625 + 11193 t + 328 t2 + 8813 + t4Подпакет SiegelTheta содержит еще одну редкую функцию:
- SiegelTheta [z, s] — возвращает значение тета-функции Зигеля Q(Z, s).
<< NumberTheory` SiegelTheta` SiegelTheta[{1+1,2+1}, {2+1,-1+41}, {1.2, 2.3+.3I}] 0.973715-0.0002970481 Sum[E^(Pi I {tl,t2}.{ {1+1,2+1}, {2+1, -1+41} }.{tl,,t2} + 2 Pi I {tl,t2}.{l.2,2.3+.31}), {tl,-10,10>, {t2,-10,10}] 0.973715 - 0.000297048 IВ заключительной части этого примера дано вычисление тета-функции Зигеля по ее исходному определению.
|