Д. Кнут - Искусство программирования том 1 (1119450), страница 17
Текст из файла (страница 17)
Покажите, что Ь щос(р равно либо О, либо 1, либо р-1. (Указание. Рассмотрите (6+1)(Ь вЂ” 1).] 27. [Мйб] Пусть и — положительное целое число н пусть 1е(и) — количество значений из множества (0,1,...,и — Ц, взаимно простых с и. Таким образом, гг(1) = 1, зг(2) = 1, 1г(3) = 2, у(4) = 2 и т. д. Покажите, что если р — простое число, то гг(р) = р — 1, и вычислите ез(р'), где е — положительное целое число. » 28. [Мйб) Покажите, что метод, который использовался для доказательства теоремы Г, можно применить для доказательства следующего ее обобщения, называемого теоремой Эйлера: если а Л. т, то а~'- ~ = 1 (по модулю т) для любого положительного целого т. (В частности, число и' из упр. 19 можно взять равным и»1 1 ' щой т.) 20.
[М22] Функция 1'(и) от положительного целочисленного аргумента и называется мультииликатнвной (тнйгр(гпгегве), если ](гз) = 1(г)1(в) для любых юаимно простых г и з. Покажите, что каждая из перечисленных ниже функций является мультипликатнвиой: (а) ф(и) = и', где с — произвольная постоянная; (Ь) 1(и) = [и не делится на к~ для любого целого Й > 1]; (с) 1(и) = с, где 6 — количество различных простых чисел, которые делят и; (4) произведение любых двух мультипликативных функций. 30.
(м80] Докажите, что функция зг(и) из упр. 27 является мультипликативной. используя этот факт, вычислите х(1000000) и предложите простой метод вычисления у(и), когда и разложено на простые множители. 31. (М22] Докажите, что если функция 1(и) мультипликативна, то д(и) = л з~„,((б) также мультиплнкатнвна. 32. [М12] Докажите, что для любой функции 1(х, 9) выполняется тождество 1(с,б) = ~ ~ ~1'(с, сб). Ы зг зц М1 33. [М10] Для целых чисел т и и вычислите: (а) [г(и+ т)1 + [г(и т+ 1).] (~) ] г(и+ т)] + Гг(и "'+1)] (Обратите внимание на частный случай гл = О.) » 34.
[М21] Какие необходимые и достаточные условия нужно наложить на действительное число Ь ) 1, чтобы равенство [)об, х] = [1об, [х] ] выполнялось для всех действительных а 17 ь Зб. [М20] Пусть гп и и — целые числа и п > О. Докажите, что равенства [(я+т)/и] = [([х]+ т)/и] выполняется для всех действительных х. (Заметикч что гп = 0 — это очень важный частный случай.) Будет ли справедливо аналогичное равенство для функции "потолок"? Зб. [МЯУ] Докажите, что ~„", [й/2] = [пз/4]; вычислите также сумму ~,", [й/2] ь ЗТ. [МЯО] Пусть гп и и — целые числа, п > О.
Покажите, что ~гпЬ+ х [ (ш — 1)(п — 1) 4 — 1 п ] 2 + + 4[я/~Ц, 2 е«ь< где Ы вЂ” наибольший общий делитель пз и п, а х — любое действительное число, 38. [Мйб] (Е. Буше (Е. Впзсйе), 1909.) Докажите, что для всех действительных чисел х и р, причем у > 0: В частности, если у †цел положительное число, то, обозначив его через п, получим важную формулу; [Х] + [х+ — ~ + + [х+ — ~ = [пх].
39. [БМ35] Функция/, для которой /(х)+/(х+ -„') + -+/(х+ — "„') = /(пх), где и— любое положительное целое число, называется реплихатиевой 1бунхцией. Из предыдущего упражнения следует, что функция [х] репликативна, Покажите, что реплнкативны следующие функции: а) /(х) = х — -', Ь) /(х) = [х — целое число]; с) /(х) = [х — положительное целое число]: б) /(х) = [существует рациональное число г и целое т, такие, что х м гя+гп]; е) еще три функции, аналогичные функции из (г(), для которых г н/или т рассматриваются только на множестве положительных чисел; 1) /(х) = (ой [2зших[, если допускается значение /(х) ж — оо; 3) сумма любых двух репликативных функций; Ь) произведение репликативной функции на константу; 1) функция 9(х) = /(х — [х]), где /(х) репликативна.
40. [НМ46] Исследуйте класс репликативиых функций; определите все репликатнвиые функции специального типа. Например, является ли функция нз и. (а) в упр. 39 единственной непрерывной репликатнвной функцией? Интересно рассмотреть также более общий класс функций, для крторых 11 / п — 1~ /(х)+/ ~х+ — /+ +/ ~х+ — ~ = а„/(пх)+Ь Здесь а и 6„— это числа, которые зависят от и, но не зависят от х. Производные и интегралы от данных функций (если Ь = 0) относятся к этому же типу. Если мы потребуем, чтобы Ь„= О, то получим, например, многочлены Бернулли, тригонометрические функции сот ях и сзс лх, а также обобщенную дзета-функцяю Гурвица ~(з, х) = 2 „>е 1ДЬ + х)', где з фиксировано. При Ь„ф 0 получим другие хорошсьмзвестные функции, например пои-функцию.
41. [МЯЯ] Пусть ам ам аз,... — последовательность 1, 2, У 3, 3, 3,4,4,4,4,.... Выразите а„как функцию от и с помощью функций 'пол" и/нли "потолок'. 42. [ЛЩ] (а) Докажите, что ал = па„— ~~ 6(аллл — ал), если п > О. Е (Ь) Предыдущая функция используется для вычисления сумм, в которых присутствует функция "пол". Докавсите, что если Ь вЂ” целое число и 6 > 2, то [1ойлк] = (п+1)[106лп] — (Ь ' '" +' — Ь)/(Ь вЂ” 1). л=1 43. [М23] Вычислите сумму 2 ь,[л/к]. 44.
[Мх4] Покажите, что 2 л>в2,<1 [(п+/Ь")/Ььл'] = п, если Ь и п — целые числа, п > 0 и 6 > 2. Чему равна эта сумма при п < 02 ь 46. [Мйв] Результат упр. 37 несколько удивляет, так как из него следует, что Е !тпй+х! Е !пй+х! Это "соотношение взаимности" — только один пример из множества подобных формул (см. раздел 3.3.3).
Покажите, что для любой функции / / (~ — !) = 2 ~ — 1 (/(г — 1) — /(г)) +и/(т — 1). о<1< В« м В частности, докажите, что ([ту/п] + 1) ч [з'п ~ ( / ) (т) [Указвмне. Выполните замену переменных г ж [т//п]. Биномиальные коэффициенты (~л) обсуждаются в разделе 1.2.6.] 46.
[Мйр] (Обобщенный закон взапмноспш.) Обобщите формулу из упр. 45 таким образом, чтобы получить выражение для суммы 2 .< „ /([ту/п]), где и — любве положительное действительное число. ь 4Т. [М31] Пусть р — нечетное простое число. Определим сомова Лезюандра, (рт), считая его равным +1, 0 или — 1, в зависимости от того, чему равно д1е Огз пюб р: 1, О или р — 1. (Слс упр.
26.) а) Пусть в не кратно р. Покажите, что числа ( — 1) щлззг1(2(сд шос1 р), 0 < 6 < р/2, сравнимы по модулю с числами 2, 4, ..., р — 1, взятыми в определенном порядке. Следовательно, (~~) = ( — 1), где в = 2 [264/р]. Ь) Используйте результат (а) для вычисления (-). 2 с) Пусть в — нечетное число. Покажите, что Хо<л<р~г[2"Я/Р] — = Ео<л<руг[ЯВ/Р] (по моЛУлю 2). [Указанне. Расслютрите величину [(Р— 1 — 2й)Я/Р] ] с() Воспользуйтесь общей формулой взаимности из упр.
46, чтобы получить закон квадратичной взаимности: (х)(-") = (-1)~" пи пгл, если р и 4 — различные нечетные простые числа. 48. [Мйб] Пусть т и и — целые числа. Докажите или опровергните следующие тожде- ства: ') ~ +и 1~ = (т1 (Ь) р +2 [ 123)~ ~ба+24 49. [МУО1 Предположим, что целочисленная функция у(х) удовлетворяет следующим двум простым условиям: (1) /(х + 1) = /(х) + 1; (й) для всех положительных целых п у(х) = Я(их))и).
Докажите, что для всех рациональных х либо у (х) = [х), либо у(х) = (х). 1.2.5. Перестановки и факториалы Перестановкой и обвекгпое называется способ последовательного расположения и различных объектов с учетом порядка. Например, для трех объектов (а, Ь, с) существует шесть перестановок: аЬс, асЬ, Ьас, Ьса, саЬ, сЬа. (1) Свойства перестановок играют очень важную роль в анализе алгоритмов; далее в этой книге мы установим много интересных фактов., касающихся перестановок (регшпгат1оп)в. А пока наша задача — просто сосчитать их, т. е. выяснить, сколько имеется возможных перестановок для и объектов.
Существует и способов выбора крайнего объекта слева (первого); после того как этот выбор сделан, существует и — 1 способ выбора следующего за ним объекта. Таким образом, получаем и(и — 1) способов выбора объектов для первых двух позиций. Аналогично третий объект можно выбрать и — 2 способами, что в итоге дает и(и — 1)(и — 2) возможных способов выбора первых трех объектов.
В общем случае, обозначив через рпь количество способов выбора Й объектов из и с учетом парилка, получим рпз = и(и — 1)...(и — х + 1). Отсюда вытекает, что общее число перестановок выражается формулой р„„= и(и — 1) ... (1). Для наших прикладных целей очень важное значение имеет процесс построения всех перестановок из и объектов методом индукции в предположении, что все перестановки из и — 1 объектов уже построены. Давайте перепишем (1), заменив буквы (а, Ь, с) цифрами (1,2, 3); тогда получим следующие перестановки: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1, (3) А теперь давайте подумаем, как из этого набора получить все возможные перестановки из четырех цифр (1,2,3,4).
Существует два основных метода перехода от перестановок из и — 1 объектов к перестановкам из и объектов. Метод 1. Для каждой перестановки аг аз ... а„ г из (1, 2.....,и — Ц объектов построим еще и перестановок, помещая число и на все возможные места, в результате чего получим и а1 аз ... а„ ы а1и аз ... а„ ы ..., аг аз .. и а„ ы аг аз ... а„ г п. * В «вязи с чрезвычайной важностью перестановок Вогвн пратт (мвпбьвп Ргаы) прелложил для краткости ивзыввть ик "реппзк. Квк только предложение Праттв будет принято, учебники по про«пяммнповвнию немного "погудеют' (и, возможно, подешевеют). Например, для перестановку 2 3 1 из (3) получим следующее: 423 1, 2431, 2 34 1, 2 3 1 4. Очевидно, это все возможные перестановки из п объектов, причем ни одна из них не повторяется.
Метод 2. Для каждой перестановки'а! а! ... а„ ! из (1, 2,...,п — 1) объектов построим еще и перестановок следующим образом. Сначала построим набор ! з / 1! /!! а2 ... /!»-! 2' а! аз ° ° ° /!» — ! 2' ' ' '' а! а2 ... а» ! (и 2)' Затем заменим элементы каждой перестановки цифрами (1,2,...,и), сохранял порядок. Например, для перестановки 2 3 1 из (3) получим и после замены получим 3421, 3412, 2413, 2314. Есть еще один способ описания этого процесса. Возьмем перестановку а!аз...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
