AOP_Tom2 (1021737), страница 204
Текст из файла (страница 204)
Более того, в соответствии с результатом упр. 4.5.3-12(с) н уравнением 4.5.3. (12) имеем Ъ'„ь~ = [рэ — РВ~ [ = 2т/РЧ ]р» — ~/РЧ ] + 0(д„~). Поэтому слелует ожидать, что поведение величины У„/2ьГР будет, по существу, аналогично поведению величины В„(х) = Ф,[р„— хе„[, где х- — случайное вещественное число. Для случайной переменной В„известна приближенная плотность распределения шш(1, В' ' — 1)/!п 2 для О < В < 1, равномерная при В < 1/2 [см.
Воюпа, Забег, Ъ!ебОЬ, 1пс!аб. Ма!5. 45 (1983), 281 — 299]. Таким образом, при обнаружении неприемлемой эффективности алгоритма Е необходимо, кроме размера величин Ъ'„, принимать во внимание какие-то дополнительные условия. 37. Примените к числу т/Р+!7 результат упр. 4.5.3-12, чтобтя увидеть, начинается ли сразу же периодическая часть дроби, и затем проверьте свойство палиндромности, вычисляя период в обратном порядке.
[Отсюда следует, что вторая часть периода дает те же значения У, что и первая, и выполнение алгоритма Е может прекратиться раньше, при выполнении шага Е5, когда о' = Г нлн У = Ъ". Однако в общем случае этот период настолько длинен, что не удается добраться до его половины; поэтому для дополнительного усложнения алгоритма оснований нет.] 38.
ПУсть г = (10ш — 1)/9. Тогда Рд — — 104э+ 9; Р~ —— г.Ь 3. 104е; Рт — — 2г+ 3 1О~ + 7; Рз = Зг+2 10~э; Р4 = 4г+2 10ээ — 3; Рэ = 5г+3 1Оээ+4; Ре = бг+2 10 +3; Рт = 7г + 2 10ы (прекрасно!); Ре = Зг + 10зэ — 7; Ре = 9г — 8000. 39. Заметим, что в случае, когда число 9 — 1 имеет 2 и р в качестве простых множителей, легко доказать, что д есть простое число.
Преемниками числа 2 являются числа Ферма, а одной из наиболее известных нерешенных задач теории чисел для этого случая является существование или отсутствие шестого простого числа Ферма. Поэтоыу мы, возможно, никогда не узнаем, как определить, имеет ли произвольное целое число каких-либо преемников. Тем не менее в некоторых случаях это возможно; например, в 1962 году Джон Селфридж (ЗоЬп Бе!(г!с(йе) доказшд что числа 78557 и 271129 таких преемников не имеют [см.
АММ 70 (1963), 101-102]. Позже Б. Серпиньский (%. 8!егр!йэЬ!) доказал существование бесконечного качнчества нечетных чисел без преемников [Е!ешеоте бег Мат!ь 15 (1960), 73 — 74]. Возможно, число 78557 является самым маленьким иэ них, хотя в настоящее время уже известно 69 претендентов на эту роль благодаря исследованиям, выполненным в 1983 году Г. йешке (О. ЗаевсЬЬе) и У. Келлером (%. Кейег) [Ма!Ь. Сошр. 40 (1983), 381-384, 661 — 673; 45 (1985), 637]. Сведения о более традиционной форме цепочек простых чисел (форме Каннингэма (Сппп!пбЬаш)), в которых переходами являются р -ч 2р ш 1, приведены в статье Гюнтера Лоха (Сбпсег Ьоб) Ма!5.
Соп1р. 53 (1989), 751-759. Б частности, он нашел, что число 554688278430 2" — 1 является простым при 0 < Ь < 12. 40. [1лб Ргос. Ьесгегэ 8 (1979), 28-31.] Заметим, что в таком абстрактном автомате х шоб 9 = х — у [х/9] может быть легко вычислено, в результате чего получим просто константы вида 0 = х — х, 1 = [х/х], 2 = 1+ 1. Убедиться в выполнении условия х ) 0 можно, проверив, будет ли х = 1 или [х/(х — 1)] Р' О. (а) Сначала за О(!об и) 1пагов вычислим ! = [!8 и] путем повторного деления на 2; одновременно вычислим Ь = 2' н А = 2э за О(!об и) циклов путем повторного присвоения ы! Ь +- 2Ь, А ь- А~.
Прежде чем выпачнять осяовные вычисления, предположим, что известны значения ! = А™, в = (.4+ 1)м и с = ш!, Теперь можно выполнить присвоения гп з- т+ 1, С +- АС, и +- (А+ Цк, о з — вт, увеличив таким образом значение т на 1; кроме того, можно йдвокть значение т путем присвоения т +- 2т, и +- из, е С вЂ” ( [и/С] гззогС А)ез, С з- Сз, учитывая, что число А является достаточно большим. (Подумайте над вариантом, когда число и представлено и системе счисления по основанию А, при этом А должно быть больше, чем (~~).) Далее, если и = (аг... ае)з, положим и, =- (ог... а,)з., если гп = и, и /г = 2з при / > О, то можно уменьшить / на 1, присвоив и з- [к/2], т з — 2гп+ ([и/И] шогС 2). Следовательно, можно вычислить число пг! для / = С, С вЂ” 1, ..., 0 за 0(1об и) циклов.
[Джулия Робинсон (Лн1(а КаЬСпзоп) предложила другое решение, а именно: вычислить и! = (В"/(в)] тогда, когда В > (2п) "+' (см. АММ 80 (1973), 250-251, 266).] згез (Ь) Сначала, как и в (а), вычисляем А = 2, затеи накопим наименьшее Сг > О, такое, что 2~т'! шобп = О. Если бсгС(п.2~!) ~ 1, полагаем /(и) равным этому значению: обратите внимание, что этот наибольший общий делитель может быть вычислен при помощи алгоритма Евклида за О(1обп) циклов. Если бсгС(п,2"!) = 1, можно найти наименьшее целое число т, такое, что ( Г ) пзогС и = О, и положить /(и) = бсг1(гп, и).
(Згчтите, что в этом случае 2" < гп < 2з+', следовательно, [т/2] < 2 и [гл/2]! взаимно просто с числом и, поэтому ( гз ) шог(п = 0 тогда и только тогда, когда гл! шодп = О. В дальнейшем и ф 4.) При ограниченном количестве регистров для вычисления т можно использовать числа Фибоначчи (см. алгоритм 6.2.1Р). Предположим, известно, что з = г» з' = Хз+г, С = А~з, С' = А~з'+', и = (А+ Цзгз, и' = (А+ Ц~'г+з, о = А, кг = (А+ Цз'", (з ) шодп ~ 0 и ( ~~~+'~) шог( и = О. Этого можно легко достичь при т = Ез~.г для достаточно больших ~' за зг~ +) О(1обп) циклов; более того, А будет больше, чем 2 Г 'Г. Если з = 1, присваиваем /(н) = зг ем боб(2ш+ 1, и) или боб(2гп 4-2, и), выбирая то из них, которое ф 1.
Выполнение алгоритма иа этом завершается. В противном случае уменьшаем 2 на 1 следующим образом: сначала присваиваем т з — з, з з — зг — з, з з — г, г з — С, С + — [С /С], С' з — г, г з- и, и +- (и'/о], и' +- г, затем, если ((иго/оС] шог( А) шогС и ~ О, присваиваем гн г- гп + з, ш з — юи, е +- ьб [Можно ли решить эту задачу за менее чем О(1об и) операций? Можно ли вычислить наименьший или наибольший простой множитель числа и за О(1об и) операцийз] 41.
(а) Очевидно, что гг(х) = зг(гп) + /г(х,гп) = "г(гл) + /(х,гп) — /гг(х,т) — /з(х, пг)— /з(х,гп) — при 1 < гп < х. Присвоим х = Х, гп = Х и учтем, что /з(Хз,Х) = 0 при Сг > 2. (Ь) ПолУчаем /з(Х Х) — 2 [Рд<зз ] — 2' ° сизгз(п(Х/Р) — л(Р) + Ц .зГз я(Х /р) — ("Г 1) + ("Г 1), где р и 9 определены на множестве простых чисел. Сл ь / ( 1 01 О) (гооо) + (зозо) + (июо) + (зоео) + (газа) + (гозо) гг(гззе) ( г 1) + Г~ ~) = 24+ 21+ 16+ 15 ч 14+ 11+ 11 55+ б = 63. (с) Приведенное в указании тождество просто означает, что р -долгожитель есть р г-долгожитель, который не кратен р, Очевидно, что /(Хгз, Х) = /(Хз, р Глг). Применяем это тождество до тех пор, пока не получим значения /(х, р,), где либо / = О, либо х < Х'.
Найдем результат: л-1 Хз Гл1 Хз /(Хз, Х) = ~~г р(к)/( —, 1) — ~ / д(/г)/( —,р, г) [И вЂ” р,-долгожитель]. з=! г=г лГХ<з<л Далее, /(х, Ц = [х], поэтому первая сумма равна 1 000 — 500 — 333 — 200 + 166 — 142 = — 9 (пРи Х = 10). ВтоРаи сУмма такова: — /('ззо,Ц вЂ” /('~з~,Ц вЂ” /('~~,2) — /('~~,2)— /( ззе,З) = — 100 — 71 — ЗЗ вЂ” 24 — 9 = -237.
Отсюда /(1000,10) = — 9+ 237 = 228 и л(1000) = 4+ 228 — 1 — 63 = 168. (6) Если Х < 2, можно сформировать массив, в котором элементы аз г+„— [и+ 1 есть р -долгожитель) для 1 < п < Хз представляют решето после / проходов, а а„ аг«+ аг вз для 1 < и < 2 . Зателс, если х < Хг, легко вычислить функцию /(х,р,) за О(т) шагов и удалить из решета числа, кратные р, за О(Хгсп/р) шагов. Общее время вычисления функции /(Хз,Х) будет равно О(Хз!обХ!о81ойХ), так как 2 ~,11/рг О(1о8! об Х). Требования к объему памяти могут быть снижены от значения 2Хггп до 2Хт, если разбить решето на Х фрагментов размером Х каждое и работать с каждым из них отдельно. Могут пригодиться вспомогательные таблицы значений р, для 1 < у < е(Х) и р(Гс), а также наименьших простых множителей чисел Гс, 1 < !с < Х, которые можно просто сформировать перед выполнением основных вычислений.
[См. Мас!г. Сопзр. 44 (1985), 537-560. Впервые подобный метод был предложен Д. Ф. Э. Мейселем (П. Р. Е. Ме!вве1, МайЛ. Аппа!есз 2 (1870), 636-642; 3 (1871), 523 .525; 21 (1883), 304; 25 (1885), 251-257. Д. П Лемер (П. Н. !в!зшег) опубликовал в журнале Ейтога е'.
МайЛ. 3 (1959), 381 388, ряд уточнений етого метода. Но ни Мейсель, ни Лемер не нашли правила, по которому рекуррентная процедура останавливалась бы с той же зффективностью, что в описанном вьппе методе. Кроме того, Лагариас (Ьабабвз) и Одлыжко (04!уз)со), используя принципы аналитической теории чисел, разработали совершенно иное приближение, посредством которого величина к(Х) может быть вычислена за О(Хмгч') сватов (см. Х А!5оНсйпзв 8 (1987), 173-191).
При помощи уточненного метода, выполняющего вычисления за О(Хыз ы) шагов, Делеглиз (Пе!еб!!ве) и Рива (и!та!) [МаНь Сагир, 65 (1996), 235 — 245) установили мировой рекорд вычисления простых чисел: я(10га) 2 220 819 602 560 918 840 42. Ь1. [Начальная установка.] Найти г, такое, что ст ш 1 (па модулю з); затем присвоить г' +- пг тес! з, и +- г г шос! з, в +- з, ш +- (и — гг )г/з шоб з, д +- [л/Х/з[, (им из) +- (1,и), (вы аз) с- (О,в).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
