Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 93
Текст из файла (страница 93)
Примечательно, что 11 111 и 8616 460 799 (по модулю 3 7 8 11), поэтому уравнение (14) справедливо и для Л/ = 11 111 за исключением случая, когда мшбгль равен 5. Поскольку прн вычислении (х~ — Л') шос(5 остатки равны 4, О, 3, 3, О, должно быть х шоб 5 = О, 1 или 4. Первая проба х > [~/М] = 106, прн которой удовлетворяются все условия, дает х = 144; но вычисление квадратного корня из числа 144г-1, 111 = 9625 не дает в результате целое число. Однако следующая проба дает 156 — 11111 = 13'225 = 115э, и в результате получаем 111П = (156 — 115) (156+ 115) = 41 271, 6. Подсчитаем число решений (х,у) конгруэнтных уравнений Л' ш (х — у)(х+ у) (по модулю р), где 0 < х,у < р.
Поскольку К ф О, а р — простое число, то х+ у у( О. Для каждого е ф О существует единственное и (по модулю р), такое, что Ю ш пе. Далее, так как р — простое число, конгруэнтные уравнения х — у ш и, х+ у ш е однозначно определяют х пес(р и у шобр. Таким образом, укаэанное выше уравнение имеет точно р — 1 решений (х,у). Если (х,у) — решение, то (х,р — у) тоже является решением при у 14 О, так как (р — у)э ш уэ: и, если (х,уг) и (х,уг) — решения, для которых у~;4 уэ, то у, ш уэ, откуда у~ = р — уэ.
Таким образом, количество различных значений х среди решений (х, у) равно (р — 1)/2, если уравнение Ю ш тэ не имеет решений, или (р+ 1)/2, если Л ш хг имеет решения. 7. Одно из возможных решений состоит в там, чтобы для каждого модуля иметь два индекса; один — для адресации текущего слова, другой — для адресации текущего бита„ загрузка двух слов таблицы и выполнение индексированной команды сдвига подравняет элементы таблицы. (Такими операциями манипулирования битами оснащены многие компьютеры.) 8.
(Можно положить, что )г' = 2М, т. е. четно.) В следующем алгоритме используется вспомогателышя таблица Х[1], Х[2],..., Х[М], где в Л [Ь] отражен признак принадлевгно- сти числа 2Й'+ 1 к простым числам. $1. Присвоить Х[Ь] +- 1 для 1 < Ь < М. Присвоить также у г- 1, р г- 3, 9 э- 4. (В ходе выполнения этого алгоритма р = 22 + 1 и 9 = 22 + 2/э.) $2, Если Х[у] = О, то перейти к шагу Я4. В противном случае вывести р, которое является простым, и присвоить Ь +- д. $3.
Если Ь < М, то присвоить Х[Ь] +- О, Ь е- Ь+ р и повторить этот шаг. $4. Присвоить у +- 2 + 1, р г- р+ 2, 9 е- 9+ 2р — 2. Если / < М, то возвратиться к шагу Я2. 3 Можно заметна ускорить ббльшую часть вычислений, если иа пшге Я4 сравнить с М не у, а 9, н добавить новый цикл, который, подавляя манипуляции р и 9, выводит 2г'+ 1 для всех оставшихся ХЦ, равных 1.
Замечание. Оригинальное решето Эратосфена было описано в книге 1, главе 13 сочинений Никомаха (ЬВсашас)пш) Ьйгог(исг1оп га Аг!гйгпег(с. Хорошо известно, что [р < Х]/р = 1и 1и Л'+ М + О(()об М) ), где М = 7+ 2,' >з п(Ь) 1п ь(Ь)/Ь вЂ” константа Мертенса, равная 0,26149 72128 47642 78375 54268 38608 69585 905 ! 6; см. Г. Мшсепз, Сге!)е 76 (1874), 46-62; Сгеепе, Кпнгй, Ьуагйешвггсз (ог гбе Ала)узм ог" А)йогййгпэ (Выгон: ВпЫгйнзет, 1981), 54.2.3.
В частности, число операций, выполняемых оригинальным алгоритмом Ннкомаха, равно Х )и )и %+О(Х). В упр. 5.2.3-1о н разделе 7.1 рассматриваются пути повышения эффективности методов просеивания для генерирования простых чисел. 9. Если рз — делитель числа п для некоторого простого числа р, то р есть делитель числа Л(п), но не числа л — 1.
Если и = рсдрп где рг < рз —. все простые числа, то рг — 1 является делителем числа Л(п), н поэтому р~рз — 1 ш О (по модулю рг — 1). Посколькг рг ш 1, то р~ — 1 кратно рз — 1, но это протнворечнт предположению, что р~ < рз. [Значения и, для которых Л(п) есть собственный делитель числа п — 1, называются числами Кармапьла (Сагписйае!). Например, приведем несколько малых чисел Кармайкла, содер.каших бшям шести множителей: 3 11 17, 5 13 17, 7.11 13 41, о 7 17 19 73. 5 7 17 73 8к 107, Имыггся 8 241 число Кармайкла, меньшее 1О'г, н существует хотя бы ()(ХЮ~) чисел Кармвйкла„ меньшнх Ф [см.
Ж. В. А!Ыб, А. Сгапг!!!е, С, Рошегапсе, Авва!з оГМагЬ. (2) 139 (1994„ 703722[. 10. Пусть Ьг — порядок числа яр по модулю и н Л вЂ” наименьшее общее кратное всех таких Ьр. Тогда Л является делителем числа и — 1, но не делителем любого (и — !)/р, поэтому Л ы и-1.
Поскольку хр " шоб п = 1, то у(п) кратно Ьр для всех р: следовательно. гоп ы(п) > Л. Но Зг(п) < и — 1, если и — не простое число. (Другой способ доказательства заключается в том, что при помощи метода, рассмотренного в упр. 3.2.1.2-!5, из элементов хр строится элемент я, нмеющий порядок и — 1.) 11.
У К А Р о У Выход 1984 1 О 992 0 1981 1981 1 992 1 1981 1983 4 495 993 0 1 993~ ш +2~ 1983 991 2 98109 1 991 1981 4 495 2 0 1 2г и +2т 1984 1981 1 99099 1 1981 1984 1 1984 99101 0 1 99101з ш +2е Разложение 199 991 получается нз первых нлн последних выходных данных. Краткость никла н появление хорошо известного числа 1984 †э, вероятно, просто совпадение.
12. В следующем алгоритме используется вспомогательная (т + 1)х (т + 1)-матрнпа с целочисленными элементамн Еуы 0 < .у, Ь < ш, входной вектор (Ье, Ьп, Ь,~ ) с элементами однократной точности н вектор (хо,кп.,.,х ) с элементами многократной точности, заданными в интервале О < яь < Х.
Р1. [Начальная установка.) Присвоить Ь; е- -1 для 0 < ! < т; затем присвоить ! з- О. Г2. [Очередное решение ) Из алгоритма Е взять очередное решение (в, ее, ем .. е .). (Алгоритмы Е н Р удобно рассматривать как сопрограммы.) Присвоить 1 г- пь Р3.
[Найти нечетное число.) Если Ь < О, перейтн к шагу РЬ. В противном случае, елн еэ четно, присвоить й +- й — 1 н повторить этот шаг. Р4, [Векторы линейно завнснмы7) Если Ьэ > О, присвоить ( < — Ьь, з < — (х;х) шоб Х е, е- е„+ Ем для 0 < г < ш; присвоить Ь +- Ь вЂ” 1 н возвратнться к шагу ГЗ. В противном случае присвоить Ьь е- У, х, е- х, Ез, <- е, для 0 < т < пп прнсвонть,у +- г + 1 н возвратиться к шагу Р2. (В последнем случае получаем новое линейно независимое решенн» по модулю 2, первым нечетным компонентом которого является еь Значения Ел могут н не быть значениями однократной точности, но они, скорее всего, будут оставаться малыми при уменьшении й от нг до 1 согласно предположениям Моррисона (Могияоп) и Бриллхарта (Впйшгг),) Еб, (Попытаться выполнить разложение.) (Тепера ео, ем ..., е, четные,) Прнпвить у+- К-1)' гор"? р' ?г) по" Л'.
Если х = у нли х+ у м Л', возвратиться к шагу г 2. В противном случае вычислить бсб(х — у, Л'), который яэляетсл собственным делителем числа Л', и завершить эыполнение алгоритма. 3 Этот алгоритм находит простые множители, когда есть возможность найти множитель из чаннога набора результатов ачгоритма Е, (Докоэот«льсшво. Пусть результатами оыполюння алгоритма Е будут (Ха Е;о,..., Е, ) при 1 < 1 < Ь и положим, что удалось найти разложение на простые множители числа Х = Х1?гэ, когда выполняются соотношения х ш А,"'... Х и у ш (-Ц"г"р",? ...р,',„~ (по модулю Л), где е? м о ~ Е1 +" +о,ЕО четно для всех ?.
Тогда х и ху (по модулю Ю1) и х гя ~у (по модулю Лэ). Нетрудно увидеть, что это решение можно преобразовать а пару (х, у), которая паяяляется прн выполнении шага РЬ, путем выполнения ряда операций, на которых пары (х,у) последовательно ммеияются парами (хх, уу'), где х' ш ху' (по модулю Л').) 13. Имеется 2 значений величины х, имеющих одинаковые показатели степени (ео,...,е, ), поскольку, если Х = у?'... до", знак величины х по модулю уд можно выбирать произвольно. Множители отсутствуют точно для двух из этих 2 значений.
14. Поскольку Рэ ш ЬЛ1'„?э (по модулю р) для любого простого делителя р числа Ъ", получим 1 ш Рнр пг' гй (ЬЛ'1~э)~р 'уэ гя (Ь?ч)~р "~э (по модулю р) при Р ~ О, 13. К, = (а" -Ь")/чу, где о = -'(Р+ чу, Ь = 1(Р-ч/Р), Р = Р' — 4Я. Тогда 2" 'К, = 2 „(ы+,)Р" Р; поэтому Ьр гй Р~р и?' (по модулю р), если р — нечетное простое число.
Аналогично, если ܄— о +Ь вЂ” У„о1 — ЯУ„, то 2 1„= ') „( ')Р э"Р и Ур щ Рр ш Р. Таким абрахом, если Ьг ш -1, получаем, что У ~1 шобр = О. Если Ь?р ш 1, то (сгЦ, ~) шабр = О. Здесь, если Я кратно р, то У„ш Р" ' (по модулю р) для и > О, поэтому К, никогда не будет кратно р; если ь) пе кратно р, то Ьгр ~ шос) р = О, Поэтому, как ив теореме Ь, К шобЛ'= О, если Лг=рг'...р',", К.Ь 4) и С = 1сш1<?б (р?~ (р?+е?)) При предположениях нз этого упражнения ранг появления числа Л' раасн Х+ 1; значит, Х взаимно проста с Я, а Г кратно Х + 1, Кроме тога, из предположений этого упражнения следует, что каждое р? является нечетным и каждое е равно ш1, поэтому 1 < 2' 'Прг? (р?+ -эр?) 2(уэ)'Ю; следовательно, г = 1 н 1 = р +е1р" ,'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
