и этот случай. Нам понадобятся
Пример 3
a[n_]:=FullSimplify[((1+Sqrt[2])^n-(1-Sqrt[2])^n)/(2Sqrt[2])] u:=a[n]+a[n-l] v:=a[n-l]
Попытаемся выполнить программу.
Do[Print[n,":",GCD{u,v]],{n,100}]
Окажется, что уже при n = 98 выражения "не хотят" упрощаться! Поэтому определение а[n_] лучше изменить.
а[n_]:=(Expand[(1+Sqrt[2])^n]-Expand[(1-Sqrt[2])^n])/(2 Sqrt[2])
Однако при таком подходе понятно, что значительное время тратится также на раскрытие скобок. Однако даже при n = 70 000 вычисления не занимают слишком много времени. При этом значении и числа u и v являются 26 794-значными, и основное время уходит на их вычисление, а не на вычисление их наибольшего общего делителя, который вычисляется в мгновенье ока! Отсюда можем сделать вывод, что функция GCD реализована весьма эффективно, и если при ее использовании возникают неприятности, то, скорее всего, они связаны с вычислением не самой функции, а ее аргументов!
Пример 6.2. Взаимная простота чисел Ферма. Числа Ферма возрастают довольно быстро и являются взаимно простыми. Поэтому их наибольший общий делитель должен быть равен 1. Выясним, до какого номера n система Mathematica сможет в приемлемое время проверить взаимную простоту этих чисел.
Вот нужная нам функция.
fermat[n_]:=2^(2^n)+1
Теперь можно написать и программу.
Do[Print(n,":",GCD[fermat[n+1], fermat[n]]],{n,100}]
Задержка начинает ощущаться при n = 28. Однако вычисления заканчиваются (и притом довольно быстро, если учитывать количество цифр в числах) и при n= 29. Напомню, что уже 22-е число Ферма имеет более миллиона (1 262 612) знаков, а 23-е число Ферма является 2 525 223-значным! Шутки ради 24-е число Ферма, являющееся 5 050 446-значным, я перетащил в Word. Текстовый редактор с записью этого числа работает медленнее, чем система Mathematica! Вот уж воистину супервычислитель: решает задачу быстрее, чем иные успевают произнести ее формулировку! 25-е число Ферма является 10 100 891-значным, и Word его не выносит: замедляется работа меню, даже курсор движется так медленно, что работать становится практически невозможно.
Пример 6.З. Взаимная простота чисел 2n -1 и 2m -1 при взаимно простых лит. Как известно, числа 2n-1 и 2m -1 взаимно просты, если взаимно просты пит. Выясним, до какого номера n(предполагая, что т<п) система Mathematica сможет в приемлемое время проверить взаимную простоту этих чисел.
Вот нужная нам функция.
fn[n_]:=2^n-1
Теперь можно написать и программу.
Dot Do[ If[GCD[n,m]==1,If[GCD[fn[n], fn[m]]!=l, Print[n,":",m]]],{m,n-l}],{n,10000}]//Timing
Для первой тысячи чисел все проверки на моем весьма слабеньком ПК выполняются всего лишь за 8,125 секунды! Правда, для проверки этого утверждения в пределах первых десяти тысяч чисел понадобится уже 3398,78 секунды. Здесь, очевидно, сказывается не только увеличение и, но и увеличение временных затрат на нахождение наибольшего общего делителя больших чисел.
Пример 6.4. Наибольший общий делитель чисел, запись которых в десятичной системе состоит из т единиц и n единиц. Как известно, наибольший общий делитель чисел, запись которых в десятичной системе состоит из m единиц и n единиц, является числом того же вида, причем количество единиц в нем равно d= НОД(n, m). Выясним, сколько времени системе Mathematica понадобится для проверки этого утверждения для n, т, не превосходящих 1000.
Вот нужные нам определения.
a111[n_]:=(10^n-1) /9 d:= GCD[n, m]
Теперь можно написать и программу.
Dot Dot If[GCD[alll[n], a111[m]]!=alll[d], Print[n,":",m]],{m,n-l}],{n,1000}]//Timing
Проверка в пределах первой сотни занимает всего лишь 0,234 секунды, хотя при этом наибольшее число указанного в условии вида имеет 100 цифр! Проверка же в пределах первой тысячи у меня потребовала в 200 раз больше — 46,594 секунды. Чтобы выполнить проверку в пределах первых пяти тысяч, потребуется 6879,67 секунды.
Пример 6.5. Наибольший общий делитель чисел аn -1 и аm -1. Как известно, наибольший общий делитель чисел аn -1 и аm -1, запись которых в системе счисления с основанием а состоит из n цифр
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий